POJ 3114 Countries in War（强联通分量+Tarjan）

浏览数：32 / 时间：2015年06月11日

题意：给你两个城市让你求最短距离，如果两个城市位于同一强连通分量中那距离为0.

思路：强连通分量缩点之后，求最短路。以前写过，总感觉记忆不深，这次自己敲完再写了一遍。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <vector>
  5 #include <stack>
  6 #include <queue>
  7 #include <algorithm>
  8 #define maxn 505
  9 using namespace std ;
 10 
 11 struct node
 12 {
 13     int u,v,w,next ;
 14 } edge[maxn*maxn];
 15 int p[maxn][maxn];
 16 int dfn[maxn],low[maxn],head[maxn] ,vis[maxn],dis[maxn],belong[maxn];
 17 int timee,cnt ,cntt,n,m;
 18 stack<int>stk ;
 19 
 20 void Init()
 21 {
 22     timee = 0 ;
 23     cnt = cntt = 0 ;
 24     memset(dfn,0,sizeof(dfn)) ;
 25     memset(low,0,sizeof(low)) ;
 26     memset(dis,0,sizeof(dis)) ;
 27     memset(head,-1,sizeof(head)) ;
 28     memset(vis,0,sizeof(vis)) ;
 29     memset(p,0x3f,sizeof(p)) ;
 30 }
 31 void addedge(int u,int v,int w)
 32 {
 33     edge[cnt].u = u ;
 34     edge[cnt].v = v ;
 35     edge[cnt].w = w ;
 36     edge[cnt].next = head[u] ;
 37     head[u] = cnt++ ;
 38 }
 39 void tarjan(int u)
 40 {
 41     //cout<<u<<endl;
 42     int v ;
 43     vis[u] = 1 ;
 44     dfn[u] = low[u] = ++ timee ;
 45     stk.push(u) ;
 46     for(int i = head[u] ; i != -1 ; i = edge[i].next)
 47     {
 48         v = edge[i].v ;
 49         if(!dfn[v])
 50         {
 51             //printf("v = %d\n",v) ;
 52             tarjan(v) ;
 53             low[u] = min(low[v],low[u]) ;
 54         }
 55         else if(vis[v])
 56             low[u] = min(low[u],dfn[v]) ;
 57     }
 58     if(low[u] == dfn[u])
 59     {
 60         cntt ++ ;
 61         do
 62         {
 63             v = stk.top() ;
 64             stk.pop() ;
 65             vis[v] = 0 ;
 66             belong [v] = cntt ;
 67          //   puts("1") ;
 68         }
 69         while(v != u) ;
 70     }
 71 }
 72 void SPFA(int u,int v)
 73 {
 74     queue<int>Q ;
 75     for(int i = 1 ; i <= cntt ; i++)
 76     {
 77         dis[i] = 999999999 ;
 78         vis[i] = 0 ;
 79     }
 80     dis[u] = 0;
 81     vis[u] = 1;
 82     Q.push(u) ;
 83     while(!Q.empty())
 84     {
 85         int s = Q.front() ;
 86         Q.pop() ;
 87         vis[s] = 0 ;
 88         for(int i = 1 ; i <= n ; i ++ )
 89         {
 90             if(p[s][i] != 999999999)
 91             {
 92                 if(dis[i] > dis[s] + p[s][i])
 93                 {
 94                     dis[i] = dis[s] + p[s][i] ;
 95                     if(!vis[i])
 96                     {
 97                         Q.push(i) ;
 98                         vis[i] = 1 ;
 99                     }
100                 }
101             }
102         }
103     }
104     if(dis[v] != 999999999)
105         printf("%d\n",dis[v]) ;
106     else printf("Nao e possivel entregar a carta\n") ;
107 }
108 void rebuild()
109 {
110     for(int i = 1 ; i <= n ; i++)
111     {
112         for(int j = head[i] ; j != -1 ; j = edge[j].next)
113         {
114          //   int s = edge[i].v ;
115             int v = belong[edge[j].v] ;
116             int u = belong[edge[j].u] ;
117             if(u != v)
118                 p[u][v] = min(p[u][v],edge[j].w) ;
119         }
120     }
121     for(int i = 1 ; i <= cntt ; i++)
122         p[i][i] = 0 ;
123 }
124 int main()
125 {
126     int x,y,h,k;
127     while(~scanf("%d %d",&n,&m))
128     {
129         if(n == 0 && m == 0) break ;
130         Init() ;
131         for(int i = 0 ; i < m ; i++)
132         {
133             scanf("%d %d %d",&x,&y,&h) ;
134             addedge(x,y,h) ;
135         }
136         for(int i = 1 ; i <= n ; i++)
137         {
138             if(!dfn[i])
139                 tarjan(i) ;
140         }
141        // cout<<"s"<<endl;
142         rebuild() ;
143        // cout<<"s"<<endl;
144         scanf("%d",&k) ;
145         for(int i = 0 ; i < k ; i++)
146         {
147             //cout<<i<<endl;
148             scanf("%d %d",&x,&y) ;
149             SPFA(belong[x],belong[y]) ;
150         }
151         printf("\n") ;
152     }
153     return 0 ;
154 }