首页 > 代码库 > P1807 最长路_NOI导刊2010提高（07）
P1807 最长路_NOI导刊2010提高（07）
洛谷——P1807 最长路_NOI导刊2010提高（07）
题目描述
设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当为G中的一条边时有i < j。设w（i，j）为边的长度，请设计算法，计算图G中<1，n>间的最长路径。
输入输出格式
输入格式：
输入文件longest.in的第一行有两个整数n和m,表示有n个顶点和m条边，接下来m行中每行输入3个整数a，b，v（表示从a点到b点有条边，边的长度为v）。
输出格式：
输出文件longest.out，一个整数，即1到n之间的最长路径.如果1到n之间没连通，输出-1。
输入输出样例
输入样例#1：
2 11 2 1
输出样例#1：
1
说明
20%的数据，n≤100，m≤1000
40%的数据，n≤1,000，m≤10000
100%的数据，n≤1,500，m≤50000，最长路径不大于10^9
思路：
求最长路？？
我们是不是都自然而然的想到了最短路？？那好，我们来想一想这个题用最短路怎么做。。
又没有人想出来呢？？
对！我们只需要我们把数组初始化为-1，然后再跑spfa求最长路就可以了！！
来看看代码？！
代码：
#include<queue>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 500005using namespace std;int x,y,z,n,m,tot,b;int head[N],dis[N];queue<int>q;bool vis[N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; }struct Edge{ int to,from,dis,next;}edge[N<<2];void add(int x,int y,int z){ tot++; edge[tot].to=y; edge[tot].dis=z; edge[tot].next=head[x]; head[x]=tot;}int spfa(int a){ for(int i=1;i<=n;i++) dis[i]=-1; dis[a]=0; vis[a]=true; q.push(a); while(!q.empty()) { b=q.front();q.pop(); for(int i=head[b];i;i=edge[i].next) { if(dis[edge[i].to]<edge[i].dis+dis[b]) { dis[edge[i].to]=edge[i].dis+dis[b]; if(!vis[edge[i].to]) q.push(edge[i].to),vis[edge[i].to]=true; } } vis[b]=false; }}int main(){ n=read(),m=read(); for(int i=1;i<=m;i++) x=read(),y=read(),z=read(),add(x,y,z); spfa(1); printf("%d",dis[n]); return 0;}
P1807 最长路_NOI导刊2010提高（07）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。