#include <queue>
#include <cstdio>
#include <iostream>
#define M 101000
#define inf 0x3f3f3f3f
using namespace std;
int start[M],e,end[M],next[M],cost[M];
inline void Init(){
	e=0;  memset(start,-1,sizeof(start));
}
inline void add(int u2,int v2,int w2){
	end[e]=v2;
	cost[e]=w2;
	next[e]=start[u2];
	start[u2]=e++;
}
int vis[M],cnt[M],d[M];
void spfa (int st,int N){
	
	memset(vis,0,N+2);
	memset(cnt,0,N+2);
	memset(d,inf,sizeof(d));
	queue<int > Q; int u1,v1, w1;
	Q.push(st), vis[st]=1, cnt[st]++, d[st]=0;
	while(!Q.empty()){
		u1=Q.front();Q.pop();vis[u1]=0;
		for(int i=start[u1];i!=-1;i=next[i]){
			v1=end[i];  w1=cost[i];
			if(d[v1]>d[u1]+w1){
				d[v1]=d[u1]+w1;
				if(!vis[v1]){
					vis[v1]=1;
					Q.push(v1);
					if(++cnt[v1]>N) return;
				}
			}
		}
	}
}
int u[M],v[M],w[M],d1[M];
int main(){
	int n,m,x;
	while(~scanf("%d%d%d",&n,&m,&x)){
     Init();
	 for(int i=0;i<m;i++){
 		scanf("%d%d%d",u+i,v+i,w+i);
 		add(u[i],v[i],w[i]);
 	}	
 	 spfa(x,n);
 	 for(int i=1;i<=n;i++)  d1[i]=d[i];
 	 Init();
 	 for(int i=0;i<m;i++)	add(v[i],u[i],w[i]);
 	 spfa(x,n);
 	 int max1=-inf;
 	 for(int i=1;i<=n;i++)
 	  if(i!=x) max1=max1<(d1[i]+d[i])?(d1[i]+d[i]):max1;
 	 printf("%d\n",max1);
	}
}

• Re:spfa 1A 水之！！附代码！！ (1384) osprey 2014-05-21 18:36:04