結果

問題 No.2712 Play more!
コンテスト
ユーザー InTheBloom
提出日時 2024-03-31 15:13:58
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 92 ms / 2,000 ms
コード長 3,253 bytes
コンパイル時間 1,821 ms
コンパイル使用メモリ 176,512 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-30 23:49:55
合計ジャッジ時間 3,592 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    int N, M; readln.read(N, M);
    auto A = readln.split.to!(int[]);

    // 辺の重みをc - Aにすると最短経路問題に帰着
    // 1を含むSCCとNを含むSCCでベルマンフォードをし、inf判定 -> infでないなら全体のグラフでベルマンフォードをする。
    // これはしんどいので、全体グラフでベルマンフォードをし、負閉路が1かNのSCCに含まれるかをみる。

    solve(N, M, A);
}

void solve (int N, int M, int[] A) {
    auto graph = new Tuple!(int, int)[][](N, 0);
    foreach (i; 0..M) {
        int a, b, c; readln.read(a, b, c);
        a--, b--;
        graph[a] ~= tuple(b, c - A[a]);
    }

    auto dist = new long[](N);
    dist[] = long.max;
    dist[0] = 0;

    // bellman-ford
    foreach (_; 0..N - 1) {
        foreach (i; 0..N) {
            if (dist[i] == long.max) continue;
            foreach (to; graph[i]) {
                int v = to[0];
                long c = to[1];
                if (dist[v] <= dist[i] + c) continue;
                dist[v] = dist[i] + c;
            }
        }
    }

    foreach (_; 0..N - 1) {
        foreach (i; 0..N) {
            if (dist[i] == long.max) continue;
            foreach (to; graph[i]) {
                int v = to[0];
                long c = to[1];

                if (dist[i] == -long.max) {
                    dist[v] = -long.max;
                    continue;
                }
                if (dist[v] <= dist[i] + c) continue;
                dist[v] = -long.max;
            }
        }
    }

    if (dist[N - 1] == -long.max) {
        writeln("inf");
    }
    else {
        writeln(-dist[N - 1] + A[N - 1]);
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

int[][] scc_decomposition (int[][] graph, int[][] revgraph)
in {
    assert(graph.length == revgraph.length, "graph.length must be equal to revgraph.length");
}
do {
    /**
     * assume:
     * 1. vertex is 0-indexed and maximum vertex number is less than graph.length
     * 2. if graph has edge (u, v), revgraph has edge (v, u).
     *
     * verified with:
     * - yosupo judge | Stringly Connected Components (https://judge.yosupo.jp/problem/scc) (LDC2/632ms/57.90Mib)
     * - AIZU ONLINE JUDGE | 強連結成分分解 (https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C)
     **/

    static bool[] vis;
    static int[] Q;

    vis.length = graph.length;
    Q.length = 0;

    void dfs (int pos) {
        vis[pos] = true;
        foreach (to; graph[pos]) {
            if (vis[to]) continue;
            dfs(to);
        }
        Q ~= pos;
    }

    foreach (i; 0..graph.length) {
        if (!vis[i]) dfs(cast(int) i);
    }

    int[][] scc;
    int idx = 0;
    vis[] = false;
    void revdfs (int pos) {
        vis[pos] = true;
        foreach (to; revgraph[pos]) {
            if (vis[to]) continue;
            revdfs(to);
        }
        scc[idx] ~= pos;
    }

    foreach_reverse (q; Q) {
        if (vis[q]) continue;
        scc ~= new int[](0);
        revdfs(q);
        idx++;
    }

    return scc;
}
0