洛谷 P1807. 最长路
原题链接
中等
作者:
我是java同学
,
2024-01-28 12:28:02
,
所有人可见
,
阅读 34
#include <bits/stdc++.h>
using namespace std;
const int N = 1510, M = 50010;
int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa() {
for (int i = 1; i <= n; i ++ )
dist[i] = -1e9;
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size()) {
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] < dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = spfa();
if (t == -1e9) puts("-1");
else cout << t << endl;
return 0;
}