[백준] 1533 길의 개수

문제 링크

http://icpc.me/1533

1533번: 길의 개수

풀이

본대 산책 2과 비슷한데 가중치가 있는 문제다.

가중치가 5 이하이기 때문에 정점을 늘려서 풀 수 있다.

정정 하나를 v0 v1 v2 v3 v4로 나누고 각 정점별 가중치를 1로 둔다. 

이때 만약 u -> v의 가중치가 3이라면 u0 -> v2 -> v1 -> v0과 같은 방식으로 u -> v의 간선을 연결할 수 있다.

이렇게 그래프를 약간 변경하여 행렬제곱을 T제곱을 하면 O((5N)^2 * logT)에 풀 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define fastio cin.tie(0)->sync_with_stdio(0)

const int mod = 1e6 + 3;
int n, s, e, t;

vvl mul(const vvl &a, const vvl &b) {
    vvl ret(5 * n, vl(5 * n, 0));
    rep(i, 0, 5 * n) rep(j, 0, 5 * n) rep(k, 0, 5 * n) {
        ret[i][j] = (ret[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
    }
    return ret;
}

vvl pw(vvl a, int t) {
    vvl ret(5 * n, vl(5 * n, 0));
    rep(i, 0, 5 * n) ret[i][i] = 1;
    while (t) {
        if (t % 2) ret = mul(ret, a);
        a = mul(a, a);
        t >>= 1;
    }
    return ret;
}

int main() {
    fastio;
    cin >> n >> s >> e >> t;
    vvl arr(5 * n, vl(5 * n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < 5; j++) {
            arr[5 * i + j][5 * i + j - 1] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < n; j++) {
            int k = s[j] - '0';
            if (k >= 1) arr[5 * i][5 * j + k - 1] = 1;
        }
    }
    arr = pw(arr, t);
    s--, e--;
    cout << arr[5 * s][5 * e];
}