Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

太感谢了!!!

Posted by 619116104 at 2013-05-18 16:01:29 on Problem 2679 and last updated at 2013-05-18 16:02:20
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator