#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多求大牛优化！！！ (1464) szwl 2014-03-05 16:55:27
  • Re:我用spfa1000ms多求大牛优化！！！ (12) szwl 2014-03-05 16:55:50