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 |
spfa 600+ms水过 队列还是用stl方便#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int inf=10000000; int first[1020],nxt[300100],from[300100],to[300100],len[300100],dis[1020],tot,n; void add(int u,int v,int l) { from[tot]=u; to[tot]=v; len[tot]=l; nxt[tot]=first[u]; first[u]=tot++; } bool spfa(int s) { queue<int>q; bool vis[1020]; int cnt[1010]; memset(cnt,0,sizeof(cnt)); memset(vis,0,sizeof(vis)); for(int i=0;i<=1000;i++) dis[i]=inf; dis[s]=0; vis[s]=1; cnt[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); vis[u]=0; q.pop(); for(int i=first[u];i!=-1;i=nxt[i]) { int v=to[i]; if(dis[v]>dis[u]+len[i]) { dis[v]=dis[u]+len[i]; if(!vis[v]) { vis[v]=1; cnt[v]++; if(cnt[v]>n) return false; q.push(v); } } } } return true; } int main() { int m,a,b,c; char ch[2]; while(cin>>n>>m) { memset(first,-1,sizeof(first)); tot=0; while(m--) { scanf("%s",&ch); if(ch[0]=='P') { scanf("%d%d%d",&a,&b,&c); add(a,b,-c); add(b,a,c); } else { scanf("%d%d",&a,&b); add(a,b,-1); } } for(int i=1;i<=n;i++) add(0,i,0); if(!spfa(0)) puts("Unreliable"); else puts("Reliable"); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator