POJ 2983 Is the Information Reliable?
#include <stdio.h>#include <string.h>#include <math.h>struct num{ int end,next,val;}a[1000000];int b[10010],sum[10010],d[10010],status[10010];int queue[1000000];int INF=0x7fffffff,n;int main(){ int spfa(); int i,j,m,s,t,x,y,val,k; char c; while(scanf("%d %d%*c",&n,&m)!=EOF) { memset(b,-1,sizeof(b)); for(i=1,j=0;i<=n;i++) { a[j].end=i; a[j].val=0; a[j].next=b[0]; b[0]=j; j++; } for(i=0;i<=m-1;i++) { scanf("%c %d %d",&c,&x,&y); if(c=='P') { scanf("%d%*c",&val); a[j].end=y; a[j].val=-1*val; a[j].next=b[x]; b[x]=j; j++; a[j].end=x; a[j].val=val; a[j].next=b[y]; b[y]=j; j++; }else { getchar(); a[j].end=y; a[j].val=-1; a[j].next=b[x]; b[x]=j; j++; } } k=spfa(); if(k) { printf("Reliable\n"); }else { printf("Unreliable\n"); } } return 0;}int spfa(){ int i,j,base,top,x,xend,k; k=1; memset(status,0,sizeof(status)); memset(sum,0,sizeof(sum)); for(i=1;i<=n;i++) { d[i]=INF; } base=top=0; d[0]=0; status[0]=1; sum[0]=1; queue[top++]=0; while(base<top) { x=queue[base++]; status[x]=0; for(j=b[x];j!=-1;j=a[j].next) { xend=a[j].end; if(d[xend]>(d[x]+a[j].val)) { d[xend]=d[x]+a[j].val; if(!status[xend]) { status[xend]=1; queue[top++]=xend; if(sum[xend]<=n-1) { sum[xend]+=1; }else { k=0; break; } } } } if(j!=-1) { break; } } return k;}
