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

题意：给你两个城市让你求最短距离，如果两个城市位于同一强连通分量中那距离为0.
思路：强连通分量缩点之后，求最短路。以前写过，总感觉记忆不深，这次自己敲完再写了一遍。
 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <algorithm>

 #define maxn 505

 using namespace std ;

 struct node

 {

     int u,v,w,next ;

 } edge[maxn*maxn];

 int p[maxn][maxn];

 int dfn[maxn],low[maxn],head[maxn] ,vis[maxn],dis[maxn],belong[maxn];

 int timee,cnt ,cntt,n,m;

 stack<int>stk ;

 void Init()

 {

     timee =  ;

     cnt = cntt =  ;

     memset(dfn,,sizeof(dfn)) ;

     memset(low,,sizeof(low)) ;

     memset(dis,,sizeof(dis)) ;

     memset(head,-,sizeof(head)) ;

     memset(vis,,sizeof(vis)) ;

     memset(p,0x3f,sizeof(p)) ;

 }

 void addedge(int u,int v,int w)

 {

     edge[cnt].u = u ;

     edge[cnt].v = v ;

     edge[cnt].w = w ;

     edge[cnt].next = head[u] ;

     head[u] = cnt++ ;

 }

 void tarjan(int u)

 {

     //cout<<u<<endl;

     int v ;

     vis[u] =  ;

     dfn[u] = low[u] = ++ timee ;

     stk.push(u) ;

     for(int i = head[u] ; i != - ; i = edge[i].next)

     {

         v = edge[i].v ;

         if(!dfn[v])

         {

             //printf("v = %d\n",v) ;

             tarjan(v) ;

             low[u] = min(low[v],low[u]) ;

         }

         else if(vis[v])

             low[u] = min(low[u],dfn[v]) ;

     }

     if(low[u] == dfn[u])

     {

         cntt ++ ;

         do

         {

             v = stk.top() ;

             stk.pop() ;

             vis[v] =  ;

             belong [v] = cntt ;

          //   puts("1") ;

         }

         while(v != u) ;

     }

 }

 void SPFA(int u,int v)

 {

     queue<int>Q ;

     for(int i =  ; i <= cntt ; i++)

     {

         dis[i] =  ;

         vis[i] =  ;

     }

     dis[u] = ;

     vis[u] = ;

     Q.push(u) ;

     while(!Q.empty())

     {

         int s = Q.front() ;

         Q.pop() ;

         vis[s] =  ;

         for(int i =  ; i <= n ; i ++ )

         {

             if(p[s][i] != )

             {

                 if(dis[i] > dis[s] + p[s][i])

                 {

                     dis[i] = dis[s] + p[s][i] ;

                     if(!vis[i])

                     {

                         Q.push(i) ;

                         vis[i] =  ;

                     }

                 }

             }

         }

     }

     if(dis[v] != )

         printf("%d\n",dis[v]) ;

     else printf("Nao e possivel entregar a carta\n") ;

 }

 void rebuild()

 {

     for(int i =  ; i <= n ; i++)

     {

         for(int j = head[i] ; j != - ; j = edge[j].next)

         {

          //   int s = edge[i].v ;

             int v = belong[edge[j].v] ;

             int u = belong[edge[j].u] ;

             if(u != v)

                 p[u][v] = min(p[u][v],edge[j].w) ;

         }

     }

     for(int i =  ; i <= cntt ; i++)

         p[i][i] =  ;

 }

 int main()

 {

     int x,y,h,k;

     while(~scanf("%d %d",&n,&m))

     {

         if(n ==  && m == ) break ;

         Init() ;

         for(int i =  ; i < m ; i++)

         {

             scanf("%d %d %d",&x,&y,&h) ;

             addedge(x,y,h) ;

         }

         for(int i =  ; i <= n ; i++)

         {

             if(!dfn[i])

                 tarjan(i) ;

         }

        // cout<<"s"<<endl;

         rebuild() ;

        // cout<<"s"<<endl;

         scanf("%d",&k) ;

         for(int i =  ; i < k ; i++)

         {

             //cout<<i<<endl;

             scanf("%d %d",&x,&y) ;

             SPFA(belong[x],belong[y]) ;

         }

         printf("\n") ;

     }

     return  ;

 }
巴特西

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

最新文章

热门文章
