首页 > > 程序设计 > C/C++ >

P1807 最长路_NOI导刊2010提高（07）

2018-06-18 04:01:51来源：未知阅读 ()

题目描述

设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：

说明

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 }