Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我用spfa1000ms多求大牛优化!!!#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"); } } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator