算法
(拓扑排序) $O(n+m)$
本题让我们求的是从点 $1$ 到点 $n$ 的最长路
一种比较好的做法是标记所有从点 $1$ 可以到达的点,只有在这些点处可以更新最长路
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<vector<P>> g(n);
vector<int> deg(n);
rep(i, m) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
g[a].emplace_back(b, c);
deg[b]++;
}
queue<int> q;
rep(i, n) if (deg[i] == 0) q.push(i);
vector<int> dp(n);
dp[n-1] = -1;
vector<bool> marked(n);
marked[0] = true;
while (q.size()) {
int v = q.front(); q.pop();
for (auto [u, w] : g[v]) {
if (marked[v]) {
chmax(dp[u], dp[v]+w);
marked[u] = true;
}
deg[u]--;
if (deg[u] == 0) q.push(u);
}
}
cout << dp[n-1] << '\n';
return 0;
}