设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 1
1 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 }