给定一个有 N 个点的有向带权无环图,现求从 1 号点到 N 号点的最长路径。
第一行有两个整数,分别代表图的点数 n 和边数 m。
第二到第 m+1 行,每行 33 个整数 u,v,w,代表存在一条从 u 到 v 边权为 w 的边。
输出一行一个整数,代表 1 到 n 的最长路。
若 1 与 n 不联通,请输出 −1。
3 4
1 3 10
1 2 5
1 2 4
2 3 7
xxxxxxxxxx
12
时间限制:1 s
内存限制:256 M
100% 的数据保证 2≤n≤1500,1≤m≤50000,−105≤w≤1052≤n≤1500,1≤m≤50000,−105≤w≤105
x
int n, m;
int cnt_edge, head[MAX_M], next[MAX_M], v[MAX_M], to[MAX_M];
inline void add_edge(int a, int b, int c) {
to[++cnt_edge] = b;
v[cnt_edge] = c;
next[cnt_edge] = head[a];
head[a] = cnt_edge;
return ;
}
//int dfs(int *x, int *f) { //判断能否到达n点
// int tx = *x, tf = *f;
// if (tx == n) return 1;
// for (int i = head[tx]; i; i = next[i]) {
// if (to[i] == tf) continue;
// if (dfs(&to[i], &tx) == 1) return 1;
// }
// return 0;
//}
int dis[MAX_N], q[MAX_M], vis[MAX_N];
inline void SPFA() {
for (int i = 1; i <= n; i++) dis[i] = -2000000000; //初始为极小值
dis[1] = 0;
vis[1] = 1;
q[0] = 1;
int l = 0, r = 1;
while (l < r) {
int tp = q[l++];
vis[tp] = 0;
for (int i = head[tp]; i; i = next[i]) {
if (dis[to[i]] >= dis[tp] + v[i]) continue;
dis[to[i]] = dis[tp] + v[i];
if (vis[to[i]]) continue;
vis[to[i]] = 1;
q[r++] = to[i];
}
}
return ;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b ,c;
scanf("%d %d %d", &a, &b, &c);
add_edge(a, b, c);
}
// int x = 1, f = 0;
// if (dfs(&x, &f) == 0) {
// printf("-1\n");
// return 0;
// }
SPFA();
printf("%d\n", dis[n] == -2000000000 ? -1 : dis[n]);
//注:使用SPFA不需要判断能否到达n点,只需初始化为极小值
return 0;
}