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);
        }
    }
}