> #include <queue>
> #include <stdio.h>
> #include <iostream>
> #include <algorithm>
> #define inf1 21644
> #define MM 1010
> #define MMM 1000004
> using namespace std;
> int N;
> int edge_num,start[MMM],end[MMM],next[MMM],cost[MMM];
> void init(){
> 	}
> void addegde (int u,int v,int w){
> 	end[edge_num]=v;
> 	cost[edge_num]=w;
> 	next[edge_num]=start[u];
> 	start[u]=edge_num++;
> }
> int cnt[MM],vis[MM],dis[MM];
> bool spfa(int c){
> 	memset(vis,false,sizeof(vis));
> 	memset(cnt,0,sizeof(cnt));
> 	memset(dis,-inf1,sizeof(dis));
> 	queue<int> Q;
> 	Q.push(0),dis[0]=0,vis[0]=1,cnt[0]++;
> 	while(!Q.empty()){
> 	 int u=Q.front();
> 	  Q.pop(),vis[u]=0;
> 	   for(int i=start[u];i!=-1;i=next[i]){
> 	    int v=end[i],w=cost[i];
> 	      if(dis[v]>dis[u]+w){
> 		 dis[v]=dis[u]+w;
> 	      if(!vis[v]){
> 		Q.push(v),vis[v]=1;
> 		if(++cnt[v]>c+1)  return 0;
> 			}
> 		}
> 	}
> 	}
> 	return 1;
> }
> int main(){
> 	int M;
> 	while(~scanf("%d%d",&N,&M)){
> 		char st[44];int u,v,w;
> 		edge_num=0;
> 	memset(start,-1,sizeof(start));
> 		while(M--){
> 		scanf("%s",st);
> 		if(st[0]=='P'){
> 			scanf("%d%d%d",&u,&v,&w);
> 			addegde(u,v,w);
> 			addegde(v,u,-w);
> 		}else{
> 		    scanf("%d%d",&u,&v);
> 			addegde(v,u,-1);	
> 		}			
> 		}
> 		for(int i=0;i<=N;i++){
> 			addegde(0,i,0);
> 		}
> 		bool Bool=spfa(N);
> 		if(Bool)  puts("Reliable");
> 		else      puts("Unreliable");
> 	}
> }

• Re:我用spfa1000ms多求大牛优化！！！ (12) szwl 2014-03-05 16:55:50