Mad Time Traveler [Kodamanと愉快な仲間たち M]

https://www.hackerrank.com/contests/kodamanwithothers/challenges/mad-time-traveler

解説

https://www.hackerrank.com/contests/kodamanwithothers/challenges/mad-time-traveler/submissions/code/1316478991

まず、時間旅行の移動を有向グラフの有向辺の置き換えると、今回の問題は有向グラフに帰着する。 各頂点は、年で表現することができる。 これで世界線変動率を最小化するようダイクストラすれば答えになりそうなものだが、これだけでは7で割ったあまりでの遷移が考慮できていない。 よって、各頂点を(年, 世界線変動率%7)で保持しておく。 これで状態数を7倍くらいに抑えつつ、遷移時の判定も行うことができる。

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int badend = 1048596;
int N, S, X;
vector<int> T[50101];
int E[50101][7];
ll D[50101][7];
bool vis[50101][7];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S >> X;
    S -= 2000;
    X -= 2000;
    
    rep(from, 1, N + 1) {
        int c; cin >> c;
        rep(j, 0, c) {
            int to; cin >> to;
            to -= 2000;
            T[from].push_back(to);
        }
    }

    rep(from, 1, N + 1) rep(m, 0, 7) cin >> E[from][m];

    rep(i, 1, N + 1) rep(mo, 0, 7) D[i][mo] = infl;
    min_priority_queue<pair<ll, int>> que;

    D[S][0] = 0;
    que.push({D[S][0], S * 10 + 0});

    while (!que.empty()) {
        auto q = que.top(); que.pop();
 
        ll cst = q.first;
        int cu = q.second / 10;
        int mo = q.second % 10;

        if (vis[cu][mo]) continue;
        vis[cu][mo] = true;
 
        fore(to, T[cu]) {
            ll cst2 = cst + E[cu][mo];
            int mo2 = cst2 % 7;

            if (chmin(D[to][mo2], cst2)) que.push({ D[to][mo2], to * 10 + mo2 });
        }
    }

    ll ans = infl;
    rep(mo, 0, 7) chmin(ans, D[X][mo]);
    if(ans == infl)
        ans = badend;
    cout << ans << endl;
}