这道题还比较正常~话说~还是那个道理，最短路径求最大值....
这题比较新的一点就是出现了三种情况
1.负环无解
2.距离太远不可达 N点未更新
3.最大值
#include<iostream>
#include<queue>
#define MAXN 2005
#define MAXM 20010
#define INF 0x7F7F7F7F
using namespace std;struct Node
{int v,price;Node *next;
}Edge[MAXM],*ptr[MAXN];int N,ML,MD;
int edgeNum;void addEdge( int u,int v,int w )
{Node *p=&Edge[edgeNum++];p->v=v;p->price=w;p->next=ptr[u];ptr[u]=p;
}int dist[MAXN];
int minV,maxV;bool spfa()
{queue<int>myQueue;int cnt[MAXN];int used[MAXN];memset( used,0,sizeof(used) );memset( cnt,0,sizeof(cnt) );memset( dist,0x7F,sizeof(dist) );dist[minV]=0;myQueue.push(minV);while( !myQueue.empty() ){int u=myQueue.front();myQueue.pop();Node *p=ptr[u];used[u]=false;while( p ){if( dist[p->v]>dist[u]+p->price ){dist[p->v]=dist[u]+p->price;if( !used[p->v] ){used[p->v]=true;myQueue.push(p->v);if( ++cnt[p->v]>N )return false;}}p=p->next;}}return true;
}int main()
{while( scanf( "%d %d %d",&N,&ML,&MD )!=EOF ){int i;int u,v,w;for( i=0;i<=N;i++ )ptr[i]=NULL;edgeNum=0;maxV=0,minV=INF;for( i=1;i<=ML;i++ ){scanf( "%d %d %d",&u,&v,&w );if( u<minV )minV=u;if( v>maxV )maxV=v;addEdge( u,v,w );}for( i=1;i<=MD;i++ ){scanf( "%d %d %d",&u,&v,&w );if( u<minV )minV=u;if( v>maxV )maxV=v;addEdge( v,u,-w );}if( !spfa() )printf( "-1\n" );else if( dist[maxV]==INF )printf( "-2\n" );elseprintf( "%d\n",dist[maxV] );}return 0;
}