poj Countries in War(强连通+最短路)

                                                                      Countries in War

题目链接：Click Here~

题目分析：

     有是一道考英语阅读理解的题。给你N个点，E个关系。如果，m个点直接形成了回路，则这m个点之间的花费是为0的。这里我们就可以想到用强连通的缩点算法了。然后，缩点后再建图，求解最短路。一开始没太在意时间。用了一个floyd TLE了。后来改成spfa就过了。改题的AC的过程真艰辛啊，虽然不是什么难题，但是调试代码用了一堆时间。看来代码能力还是好弱啊。

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 500+5;
const int INF = 1e8;
int n,m,graph[maxn][maxn],d[maxn][maxn];
int pre[maxn],sccno[maxn],lowlink[maxn];
int scc_cnt,dfs_clock;
vector<int> G[maxn];
stack<int> S;
void Init()
{
    while(!S.empty())S.pop();
    for(int i = 0;i < maxn;++i)
       G[i].clear();
    for(int i = 0;i < maxn;++i)
      for(int j = 0;j < maxn;++j)
          d[i][j] =(i==j?0:INF),graph[i][j] = (i==j?0:INF);
}
void dfs(int u)
{
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for(int i = 0;i < (int)G[u].size();++i){   
       int v = G[u][i];                          
       if(!pre[v]){
          dfs(v);
          lowlink[u] = min(lowlink[u],lowlink[v]);
       }
       else
       if(!sccno[v])
          lowlink[u] = min(lowlink[u],pre[v]);
    }
    if(pre[u]==lowlink[u]){
       int x;
       scc_cnt++;
       do
       {                           
           x = S.top();              
           S.pop();
           sccno[x] = scc_cnt;       
       }while(x!=u);               //attention!!!
    }
}
void find_scc()
{
    scc_cnt = dfs_clock = 0;
    memset(pre,0,sizeof(pre));
    memset(sccno,0,sizeof(sccno));
    for(int i = 1;i <= n;++i)
      if(!pre[i])dfs(i);
}
int Spfa(int s,int e)
{
    queue<int> Q;
    int dist[maxn];
    bool inq[maxn];
    memset(inq,0,sizeof(inq));
    for(int i = 0;i <= n;++i)
      dist[i] = INF;
    dist[s] = 0;
    Q.push(s);
    while(!Q.empty()){
       int u = Q.front();
       Q.pop();
       inq[u] = false;
       for(int i = 1;i <= n;++i)if(d[u][i]!=INF){
            if(dist[i] > dist[u]+d[u][i]){
                dist[i] = dist[u]+d[u][i];
                if(!inq[i]){
                   inq[i] = true;
                   Q.push(i);
                }
            }
       }
    }
    return dist[e];
}
int main()
{
//    freopen("Input.txt","r",stdin);
    while(scanf("%d%d",&n,&m),(n||m))
    {
        Init();
        int u,v,c;
        while(m--){
           scanf("%d%d%d",&u,&v,&c);
           G[u].push_back(v);
           graph[u][v] = c;
        }
        find_scc();           
        for(int u = 1;u <= n;++u)       //缩点
          for(int i = 0;i < (int)G[u].size();++i){
             int v = G[u][i];
             if(sccno[u]!=sccno[v]){
                 if(d[sccno[u]][sccno[v]] > graph[u][v])
                    d[sccno[u]][sccno[v]] = graph[u][v];
             }
          }
        int q;
        scanf("%d",&q);
        while(q--){
           scanf("%d%d",&u,&v);
           int ans = Spfa(sccno[u],sccno[v]);
           if(ans==INF)
             puts("Nao e possivel entregar a carta");
           else
             printf("%d\n",ans);
        }
        puts("");
    }
    return 0;
}

poj Countries in War(强连通+最短路),布布扣,bubuko.com

poj Countries in War(强连通+最短路)

原文：http://blog.csdn.net/zhongshijunacm/article/details/21632253