Late Edges [CSAcademy #54]

https://csacademy.com/contest/round-54/task/late-edges/

N頂点の無向グラフがある。
辺には利用可能になる時間が書いてある。
最初は時間0で頂点0スタート。
各時間で必ず隣接点に移動する必要があるときに、最短何秒で頂点(N-1)に到達できるか。
N,M≦5*10^3

解説

「mi[i][j] := 頂点iに到達できるパリティがjの時の最短時間」を使って最短距離を更新していく。
パリティがjとは最短時間のパリティのことである。
　

• 時間5に頂点iにいる
  • それにつながっている利用時間が9である辺を渡れる最短時間は？
    • 横の頂点と行ったり来たりすれば5->7->9でピッタリに渡れる
  • それにつながっている利用時間が10である辺を渡れる最短時間は？
    • 横の頂点と行ったり来たりすると5->7->9->11で1秒遅れで渡れる

　
つまり、パリティが一致しているかどうかで1秒遅れかどうか分かる。
そのため、到達できる最短時間を保持しておくが、偶数での最短時間と奇数での最短時間に分けて保持する。
　
あとは、時間が早い順に辺を追加しておき、辺の追加毎に深さ優先っぽい探索でmi変数を更新していけばいい。
深さ優先っぽいと書いたのは、配列miが更新できる場合のみ探索していく探索であるからである。
こうすれば、辺を追加ごとに更新される状態数はN*2状態であり、辺を追加はM回なので、O(MN)で間に合う。

int N, M;
using T = tuple<int, int, int>;
vector<T> E;
vector<int> EE[5010];
//---------------------------------------------------------------------------------------------------
#define INF INT_MAX/2
int mi[5010][2];
void dfs(int cu, int t) {
    if (t < mi[cu][t % 2]) {
        mi[cu][t % 2] = t;

        fore(to, EE[cu]) dfs(to, t + 1);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        E.push_back(T(c, a, b));
    }
    sort(E.begin(), E.end());

    rep(i, 0, N) mi[i][0] = mi[i][1] = INF;
    mi[0][0] = 0;

    fore(t, E) {
        int a, b, c;
        tie(c, a, b) = t;
        EE[a].push_back(b);
        EE[b].push_back(a);

        rep(i, 0, 2) {
            if (mi[a][i] != INF) {
                if (c <= mi[a][i]) dfs(b, mi[a][i] + 1);
                else dfs(b, c + 1 + (mi[a][i] % 2 != c % 2));
            }
            if (mi[b][i] != INF) {
                if (c <= mi[b][i]) dfs(a, mi[b][i] + 1);
                else dfs(a, c + 1 + (mi[b][i] % 2 != c % 2));
            }
        }
    }

    int ans = min(mi[N - 1][0], mi[N - 1][1]);
    if (ans == INF) ans = -1;
    printf("%d\n", ans);
}