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 |
太感谢了!!!In Reply To:Some Parts Of Data! Posted by:TaurenChieftain at 2009-05-25 20:23:12 都是一针见血的数据啊! AC code: #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <cmath> #include <algorithm> using namespace std; const int maxn=1200; const int maxm=5100; const int inf=1000000000; int n,m,L1,L2,S,T; int E1[2*maxm],p1[2*maxm],w1[2*maxm],pre1[2*maxm],flag[2*maxm],fst1[maxn]; int E2[2*maxm],p2[2*maxm],w2[2*maxm],pre2[2*maxm],fst2[maxn]; int vis1[maxn],vis2[maxn],dist1[maxn],dist2[maxn],cnt[maxn],q[maxn]; void add1(int a,int b,int c,int d) { E1[L1]=b; p1[L1]=c; w1[L1]=d; pre1[L1]=fst1[a]; fst1[a]=L1++; } void add2(int a,int b,int c,int d) { E2[L2]=b; p2[L2]=c; w2[L2]=d; pre2[L2]=fst2[a]; fst2[a]=L2++; } void bfs() { memset(vis1,0,sizeof(vis1)); int head=1,tail=2; q[1]=T; vis1[T]=1; while(head<tail) { int u=q[head]; for(int k=fst1[u];k!=-1;k=pre1[k]) if(flag[k] && !vis1[E1[k]]) vis1[E1[k]]=1,q[tail++]=E1[k]; head++; } } bool cmp(int u,int v,int k) { if(dist1[u]+p2[k]<dist1[v]) return true; if(dist1[u]+p2[k]==dist1[v] && dist2[u]+w2[k]<dist2[v]) return true; return false; } bool spfa() { for(int i=0;i<=n;i++) vis2[i]=cnt[i]=0,dist1[i]=dist2[i]=inf; int head=1,tail=2; q[1]=S; vis2[S]=cnt[S]=1; dist1[S]=dist2[S]=0; while(head!=tail) { int u=q[head]; for(int k=fst2[u];k!=-1;k=pre2[k]) if(vis1[E2[k]] && cmp(u,E2[k],k)) { if(E2[k]==u) return true; dist1[E2[k]]=dist1[u]+p2[k]; dist2[E2[k]]=dist2[u]+w2[k]; if(!vis2[E2[k]]) { vis2[E2[k]]=1; cnt[E2[k]]++; if(cnt[E2[k]]>n) return true; q[tail++]=E2[k]; if(tail>n) tail-=n; } } vis2[u]=0; head++; if(head>n) head-=n; } return false; } int main() { int a,b,c1,c2,d; while(scanf(" %d%d%d%d",&n,&m,&S,&T)!=EOF) { if(n==0 || m==0) {printf("0 0\n"); continue;} S++; T++; L1=L2=0; memset(flag,0,sizeof(flag)); for(int i=0;i<=n;i++) fst1[i]=fst2[i]=-1; for(int i=1;i<=m;i++) { scanf(" (%d,%d,%d[%d]%d)",&a,&b,&c1,&d,&c2); a++; b++; add1(a,b,c1,d); add1(b,a,c2,d); } for(int i=1;i<=n;i++) { int minx=inf; for(int k=fst1[i];k!=-1;k=pre1[k]) if(p1[k]<minx) minx=p1[k]; for(int k=fst1[i];k!=-1;k=pre1[k]) if(p1[k]==minx) add2(i,E1[k],p1[k],w1[k]),flag[k^1]=1; } bfs(); if(spfa()) printf("UNBOUND\n"); else if(dist1[T]==inf) printf("VOID\n"); else printf("%d %d\n",dist1[T],dist2[T]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator