题解 ABC 061 D

zerc · 2022-10-20 15:38:09 · 题解

题意很显然，让你求最长路或“找正环”。

然后边权转负就成了最短路+找负环，用死掉了 SPFA 跑一遍就好了，

然后你会发现 WA 了，我们的思路好像并没有问题，再读一遍题：

If it is possible to increase the score indefinitely, print inf.

如果分数可以无限增加，输出 inf 。

分数无限增加一定是有正环，但有正环分数就一定会无限增加么？

如果有一个正环，但从 1 到 n 的路径上并不会经过，那么他对答案是没有影响的，

所以开始时说的“找正环”是不对的，应该是 找最长路径上是否经过正环，

这样我们只需要判断 n 是否在正环上就可以了。

bool spfa() {
    for (int i = 2; i <= n; i++) dis[i] = inf;
    dis[1] = 0, vis[1] = 1, q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = 0;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (inq[v]) continue;
            if (dis[v] > dis[u] + e[i].val) {
                dis[v] = dis[u] + e[i].val;
                if (!vis[v]) {
                    vis[v] = 1, q.push(v);
                    if (++tot[v] >= n) {
                        inq[v] = 1;  // 标记负环
                    }
                }
            }
        }
    }
    return inq[n];
}

完整代码