poj 3114 Countries in War

http://poj.org/problem?id=3114
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <algorithm>
  5 #define maxn 300000
  6 using namespace std;
  7 
  8 const int inf=1<<30;
  9 int head[maxn],head1[maxn],dfn[maxn],low[maxn],belong[maxn],stack1[maxn],dis[maxn],cnt[maxn];
 10 int e,ee,bcc_clock,bcnt,top,N,E,x,y,h,k,o,d;
 11 bool vis[maxn],visi[maxn];
 12 
 13 struct node
 14 {
 15     int u,v,w,next;
 16 }p[maxn];
 17 
 18 struct node1
 19 {
 20     int u,v,w,next;
 21 }pp[maxn];
 22 
 23 void add(int u,int v,int w)
 24 {
 25     p[e].u=u;
 26     p[e].v=v;
 27     p[e].w=w;
 28     p[e].next=head[u];
 29     head[u]=e++;
 30 }
 31 
 32 void addnode(int u,int v,int w)
 33 {
 34     pp[ee].u=u;pp[ee].v=v;
 35     pp[ee].w=w;
 36     pp[ee].next=head1[u];
 37     head1[u]=ee++;
 38 }
 39 
 40 void tarjan(int u)
 41 {
 42     vis[u]=true;
 43     dfn[u]=low[u]=++bcc_clock;
 44     stack1[++top]=u;
 45     for(int i=head[u]; i!=-1; i=p[i].next)
 46     {
 47         int v=p[i].v;
 48         if(!dfn[v])
 49         {
 50             tarjan(v);
 51             low[u]=min(low[u],low[v]);
 52         }
 53         else if(vis[v])
 54         {
 55             low[u]=min(low[u],dfn[v]);
 56         }
 57     }
 58     if(dfn[u]==low[u])
 59     {
 60         bcnt++;
 61         int j;
 62         do
 63         {
 64             j=stack1[top--];
 65             vis[j]=false;
 66             belong[j]=bcnt;
 67         }while(j!=u);
 68     }
 69 }
 70 
 71 void deal()
 72 {
 73    bcc_clock=0,bcnt=0,top=0;
 74    memset(vis,false,sizeof(vis));
 75    memset(belong,0,sizeof(belong));
 76    memset(dfn,0,sizeof(dfn));
 77    for(int i=1; i<=N; i++)
 78    {
 79        if(!dfn[i])
 80        {
 81            tarjan(i);
 82        }
 83    }
 84 }
 85 
 86 void inti()
 87 {
 88     memset(head,-1,sizeof(head));
 89     memset(head1,-1,sizeof(head1));
 90     e=0,ee=0;
 91 }
 92 bool ralex(int u,int v,int w)
 93 {
 94     if(dis[v]>dis[u]+w)
 95     {
 96         dis[v]=dis[u]+w;
 97         return true;
 98     }
 99     return false;
100 }
101 
102 bool spfa(int src)
103 {
104     memset(visi,false,sizeof(visi));
105     memset(cnt,0,sizeof(cnt));
106     queue<int>q;
107     for(int i=0; i<=N; i++)
108     {
109         dis[i]=inf;
110     }
111     dis[src]=0;
112     visi[src]=true;
113     q.push(src);
114     while(!q.empty())
115     {
116         int u=q.front();q.pop();
117         visi[u]=false;
118         for(int i=head1[u]; i!=-1; i=pp[i].next)
119         {
120             if(ralex(u,pp[i].v,pp[i].w)&&!visi[pp[i].v])
121             {
122                 if((++cnt[pp[i].v])>N) return false;
123                 visi[pp[i].v]=true;
124                 q.push(pp[i].v);
125             }
126         }
127     }
128     return true;
129 }
130 
131 int main()
132 {
133     while(scanf("%d%d",&N,&E)!=EOF)
134     {
135         inti();
136         if(N==0&&E==0) break;
137         for(int i=0; i<E; i++)
138         {
139             scanf("%d%d%d",&x,&y,&h);
140             add(x,y,h);
141         }
142         deal();
143         for(int i=1; i<=N; i++)
144         {
145             for(int j=head[i]; j!=-1; j=p[j].next)
146             {
147                 int v=p[j].v;
148                 if(belong[i]==belong[v]) addnode(i,v,0);
149                 else if(belong[i]!=belong[v]) addnode(i,v,p[j].w);
150             }
151         }
152         scanf("%d",&k);
153         for(int i=0; i<k; i++)
154         {
155             scanf("%d%d",&o,&d);
156             spfa(o);
157             if(dis[d]!=inf)
158                 printf("%d
",dis[d]);
159             else
160                 printf("Nao e possivel entregar a carta
");
161         }
162         printf("
");
163     }
164     return 0;
165 }
View Code