题目描述
设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
Solution:
本题裸的最短路，直接将dis数组初始赋值为-inf，将三角不等式改为dis[v]<dis[u]+val[u]，最后输出时判断下-1的情况就ok了。
代码：
#include<bits/stdc++.h> #define il inline #define ll long long #define debug printf("%d %s ",__LINE__,__FUNCTION__) using namespace std; const int N=200005,inf=-233333333; int n,m,h[N],to[N],net[N],cnt,dis[N],val[N]; bool vis[N]; il int gi() { int a=0;char x=getchar();bool f; while((x<'0'||x>'9')&&x!='-')x=getchar(); if(x=='-')x=getchar(),f=1; while(x>='0'&&x<='9')a=a*10+x-48,x=getchar(); return f?-a:a; } il void add(int u,int v,int w) { to[++cnt]=v,net[cnt]=h[u],val[cnt]=w,h[u]=cnt; } il void spfa() { queue<int>q; for(int i=1;i<=n;i++)dis[i]=inf; dis[1]=0;vis[1]=1;q.push(1); while(!q.empty()) { int u=q.front();q.pop();vis[u]=0; for(int i=h[u];i;i=net[i]) if(dis[to[i]]<dis[u]+val[i]){ dis[to[i]]=dis[u]+val[i]; if(!vis[to[i]])q.push(to[i]),vis[to[i]]=1; } } } int main() { // n=gi(),m=gi(); scanf("%d%d",&n,&m); int u,v,w; for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); } spfa(); printf("%d",dis[n]==inf?-1:dis[n]); return 0; }