首页 > 代码库 > 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
裸SPFA
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=500001; 8 struct node 9 {10 int u;11 int v;12 int w;13 int next;14 }edge[MAXN];15 int num=1;16 int head[MAXN];17 void add(int x,int y,int z)18 {19 edge[num].u=x;20 edge[num].v=y;21 edge[num].w=z;22 edge[num].next=head[x];23 head[x]=num++;24 }25 int dis[MAXN];26 int vis[MAXN];27 int n,m,s;28 void SPFA(int s)29 {30 dis[s]=0;31 vis[s]=1;32 queue<int>q;33 q.push(s);34 while(q.size()!=0)35 {36 int p=q.front();37 q.pop();38 vis[p]=0;39 for(int i=head[p];i!=-1;i=edge[i].next)40 {41 int to=edge[i].v;42 if(dis[to]<dis[p]+edge[i].w)43 {44 dis[to]=dis[p]+edge[i].w;45 if(vis[to]==0)46 {47 q.push(to);48 vis[to]=1;49 }50 }51 }52 }53 if(dis[n]==0)54 printf("-1");55 else 56 printf("%d ",dis[n]); 57 }58 int main()59 {60 61 scanf("%d%d",&n,&m);62 for(int i=1;i<=n;i++)63 head[i]=-1,dis[i]=0;64 for(int i=1;i<=m;i++)65 {66 int x,y,z;67 scanf("%d%d%d",&x,&y,&z);68 add(x,y,z);69 }70 SPFA(1);71 return 0;72 }
P1807 最长路_NOI导刊2010提高（07）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。