题解：P1807 最长路

int_stl · 2024-07-20 19:45:28 · 题解

我们可以使用 SPFA 解决这道题目。

我们容易发现，当我们跑完最短路后，一定会有 d_v \ge d_u + w(v \in \text{son}(u))，那么我们只要把最短路的判断条件改为 d_v 是否小于 d_u + w 即可。

SPFA 最坏时间复杂度为 O(nm)，足以通过此题了。

参考代码如下：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector < pair <int, int> > e[1504];
queue <int> q;
long long dis[1504];
bool vis[1504];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
    }
    q.push(1);
    for (int i = 1; i <= n; i++) {
        dis[i] = -1145141919810;
    }
    dis[1] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto [v, w] : e[u]) {
            if (dis[v] < dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);  
                }
            }
        }
    }
    cout << (dis[n] == -1145141919810 ? -1 : dis[n]);
}