题目描述
题目描述
设 GG 为有 nn 个顶点的带权有向无环图，GG 中各顶点的编号为 11 到 nn，请设计算法，计算图 GG 中 1, n1,n 间的最长路径。
输入格式
输入的第一行有两个整数，分别代表图的点数 nn 和边数 mm。
第 22 到第 (m + 1)(m+1) 行，每行 33 个整数 u, v, wu,v,w（u<vu<v），代表存在一条从 uu 到 vv 边权为 ww 的边。
输出格式
输出一行一个整数，代表 11 到 nn 的最长路。
若 11 与 nn 不连通，请输出 -1−1。
输入输出样例
输入 #1复制
2 1 1 2 1输出 #1复制
1说明/提示
【数据规模与约定】
- 对于 20%20%的数据，n \leq 100n≤100，m \leq 10^3m≤103。
- 对于 40%40% 的数据，n \leq 10^3n≤103，m \leq 10^{4}m≤104。
- 对于 100%100% 的数据，1 \leq n \leq 15001≤n≤1500，1 \leq m \leq 5 \times 10^41≤m≤5×104，1 \leq u, v \leq n1≤u,v≤n，-10^5 \leq w \leq 10^5−105≤w≤105。
拓扑排序算法求解
分析
如果题目不限制从1出发，到n，求到某个点的最长路径，那么直接进行拓扑排序，然后每次更新就可以了
但是题目说了从1到n最长路径，那么这个路径之外的点都不用管，所以只更新1能到达的点的最长路径值就可以了
-
在拓扑排序过程中同步标记1能到的点
-
然后所有点正常拓扑排序，但是更行1到每个点最大值的时候，只需要更新1能到的点的就行，其他1不能到达的点不用管
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int N = 1510;
struct Edge
{
int to;
int w; //从该点到to点的边的权重
};
vector<Edge> h[N]; //存图
int d[N]; // 入度
int n, m;
bool st[N]; // 标记1能到的点 为 true
int maxx[N]; // 从1能到该点的路径最大值
void add(int a, int b, int weight)
{
Edge edge;
edge.to = b;
edge.w = weight;
h[a].push_back(edge);
}
void tor()
{
// q存节点编号，用int就行
queue<int> q;
for(int i = 1; i <= n; i++)
{
// 如果该点的入度为0，加入队列中
if(!d[i]) q.push(i);
}
while(!q.empty())
{
int t = q.front();
q.pop();
for(int i = 0; i < h[t].size(); i++)
{
int j = h[t][i].to;
int weight = h[t][i].w;
// 标准拓扑操作
d[j]--;
if(!d[j]) q.push(j);
// 如果1能到t点
if(st[t])
{
st[j] = true; // 那么也一定能到j点，这个时候再更新j点的最大距离
maxx[j] = max(maxx[j], maxx[t] + weight);
}
}
}
}
int main()
{
memset(maxx, -1, sizeof maxx); // 初始化到1每个点的最大距离为-1
scanf("%d%d", &n, &m);
while(m--)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
add(a, b, w); // a -> b
d[b]++; //
}
maxx[1] = 0;
st[1] = true;
tor();
printf("%d\n", maxx[n]);
return 0;
}
时间复杂度
参考文章
https://www.luogu.com.cn/blog/AcerMo/solution-p1807