题目描述

设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
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           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
          
           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]