57 lines
1.9 KiB
C++
57 lines
1.9 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
//拓扑排序+vector实现
|
||
const int N = 50000 + 10;
|
||
const int INF = 0x3f3f3f3f;
|
||
|
||
//结构体
|
||
struct Edge {
|
||
int to; //下一个结点
|
||
int value; //边长
|
||
int next; //索引值
|
||
};
|
||
vector<Edge> p[N];
|
||
|
||
int ind[N]; //入度
|
||
int f[N]; //动态规划的结果
|
||
queue<int> q; //拓扑排序用的队列
|
||
int n; //n个顶点
|
||
int m; //m条边
|
||
|
||
int main() {
|
||
//读入
|
||
cin >> n >> m;
|
||
for (int i = 1; i <= m; ++i) {
|
||
int u, v, w;//代表存在一条从 u 到 v 边权为 w 的边。
|
||
cin >> u >> v >> w;
|
||
p[u].push_back({v, w});
|
||
ind[v]++;//统计入度个数
|
||
}
|
||
//入度为0的结点入队列，进行拓扑排序
|
||
for (int i = 1; i <= n; i++) if (!ind[i]) q.push(i);
|
||
|
||
//初始化,将到达节点1的距离设为最大值,这个用的太妙了~~
|
||
//防止出现负权边，也防止出现了0不知道是权边加在一起出现的，还是天生就是0
|
||
//调高起点值看来是解决负权边的重要方法，学习学习。
|
||
f[1] = INF;
|
||
|
||
//拓扑排序
|
||
while (!q.empty()) {
|
||
int u = q.front();
|
||
q.pop();
|
||
//遍历每条出边
|
||
for (int i = 0; i < p[u].size(); i++) {
|
||
int y = p[u][i].to;
|
||
--ind[y]; //在删除掉当前结点带来的入度
|
||
//精髓！~
|
||
//运用拓扑排序的思想,对每个节点进行访问,并在此处用上动态规划的思路更新到此节点的最大距离
|
||
f[y] = max(f[y], f[u] + p[u][i].value); //利用走台阶思路，从上一级走过来
|
||
if (!ind[y]) q.push(y);//在删除掉当前结点带来的入度后，是不是入度为0了，如果是将点y入队列
|
||
}
|
||
}
|
||
//如果可以到达，则输出最长路径
|
||
if (f[n] > 0)printf("%d", f[n] - INF);
|
||
else printf("-1");
|
||
return 0;
|
||
} |