| ||||||||||
| 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