CWOI J C103 D 觀者

給定一個 $n$ 個點 $m$ 條邊的有向圖（$1 \le n, m \le 10^6$），每條邊又一個權值 $w$（$0 \le w \le 10^9$）。對於每一個起點，如果能經過每一個節點，輸出 Infinity，否則輸出能經過最多節點的字典序最小的路徑 $w_1,w_2,\cdots,w_k$ 的計算值： $\sum^{k}_{i=1}w_i\times 29^i \pmod{998244353}$。

先不考慮字典序，容易想到建反向邊拓撲排序，如果拓撲排序排完後入度不為 0，則最長路是無限長，否則令 $f(i)$ 表示 $i$ 的最長路長度，$g(i)$ 表示最長路的計算值，按照拓撲排序轉移即可。

如果發現一條長度相同的新路徑，可以採用雜湊+倍增的方法比較字典序。記 $h(i, j)$ 表示從 $i$ 出發向後 $2^j$ 步的雜湊值，$r(i, j)$ 表示從 $i$ 出發第 $2^i$ 步的位置。利用雜湊值快速找到第一個新老路徑不同的邊權，再比較大小。

注意：

1. 最好不要用 $\sum^{k}_{i=1}w_i\times 29^i \pmod{998244353}$ 做雜湊，容易被別有用心的出題人卡。
2. 如果用了題目給的雜湊，要注意模數是 $998244353$，而邊權最大值是 $10^9$，找到不同邊權後比較大小也不能直接比較 $h(i, 0)$。
3. 為了方便更新比較兩條路徑，再拓撲排序更新時，可能會需要計算幾個長度固定為 20（$2^{20} > 10^6$）的陣列，推薦使用 std::array 而不是 std::vector，std::vector 在堆上而 std::array 在棧上，後者通常快於前者。可參考：知乎 C++ 中 vector 和 array 效能差異究竟有多大？，

完整程式碼：

#include <algorithm>
#include <array>
#include <cctype>
#include <cstdio>
#include <queue>
#include <vector>

const long long MOD1 = 998244353;
const long long MOD2 = 1000000009;

template <typename T> T read()
{
    T x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -f;
        c = getchar();
    }
    while (isdigit(c)) {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

struct edge_t
{
    int v;
    long long w;
    edge_t() {}
    edge_t(int v, long long w) : v(v), w(w) {}
};

long long base1[1 << 20], base2[1 << 20];

int main()
{
    base1[0] = base2[0] = 1;
    for (int i = 1; i < (1 << 20); i++) base1[i] = base1[i - 1] * 29 % MOD1;
    for (int i = 1; i < (1 << 20); i++) base2[i] = base2[i - 1] * 314159 % MOD2;

    int n, m;
    n = read<int>();
    m = read<int>();
    std::vector<std::vector<edge_t>> g(n);
    std::vector<int> indeg(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        long long w;
        x = read<int>();
        y = read<int>();
        w = read<long long>();
        x--;
        y--;
        g[y].emplace_back(x, w);
        indeg[x]++;
    }

    std::vector<int> len(n);
    std::vector<std::array<int, 20>> next(n);
    std::vector<long long> route(n);
    std::vector<std::array<long long, 20>> hash(n);
    std::queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0) {
            q.emplace(i);
            len[i] = 1;
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto [v, w] : g[u]) {
            if (len[u] + 1 >= len[v]) {
                std::array<int, 20> new_next;
                long long new_route;
                std::array<long long, 20> new_hash;
                new_next[0] = u;
                new_hash[0] = w % MOD2;
                for (int i = 1; i < 20; i++) {
                    new_next[i] = next[new_next[i - 1]][i - 1];
                    new_hash[i] = (hash[new_next[i - 1]][i - 1] * base2[1 << (i - 1)] % MOD2 +
                                   new_hash[i - 1]) %
                                  MOD2;
                }
                new_route = (route[u] * base1[1] % MOD1 + w) % MOD1;
                if (len[u] + 1 == len[v]) {
                    int x = v, y = v;
                    for (int i = 19; i >= 0; i--) {
                        if (y == v) {
                            if (hash[x][i] == new_hash[i]) {
                                x = next[x][i];
                                y = new_next[i];
                            }
                        } else {
                            if (hash[x][i] == hash[y][i]) {
                                x = next[x][i];
                                y = next[y][i];
                            }
                        }
                    }
                    if (y == v) {
                        if (hash[x][0] > new_hash[0]) {
                            for (int i = 0; i < 20; i++) {
                                next[v][i] = new_next[i];
                                hash[v][i] = new_hash[i];
                            }
                            route[v] = new_route;
                        }
                    } else {
                        if (hash[x][0] > hash[y][0]) {
                            for (int i = 0; i < 20; i++) {
                                next[v][i] = new_next[i];
                                hash[v][i] = new_hash[i];
                            }
                            route[v] = new_route;
                        }
                    }
                } else {
                    for (int i = 0; i < 20; i++) {
                        next[v][i] = new_next[i];
                        hash[v][i] = new_hash[i];
                    }
                    route[v] = new_route;
                    len[v] = len[u] + 1;
                }
            }
            indeg[v]--;
            if (indeg[v] == 0) q.emplace(v);
        }
    }
    for (int i = 0; i < n; i++) {
        if (indeg[i] != 0) puts("Infinity");
        else {
            printf("%lld\n", route[i] * 29 % MOD1);
        }
    }
}