POJ Countries in War 3114

题目大意：

给定一些城市，然后再给一些寄信的路信，A，B，H代表把信从A城市寄到B城市需要H小时。

如果没有直接可以寄达的，可以先通过另外一个城市到达，比如A，B可以寄信，B，C可以寄信，那么，A，C也可以寄信。

其中两个城市之间如果可以相互寄信的话，那么这两个城市是属于一个国家的，寄信可以通过电子邮件，所以所需的时间为0.

题目中有K个询问，输入A，B询问A到B之间寄信最少需要多少时间

题目分析：

先求出强联通然后构图求最短路。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <queue>

usingnamespace std;

#define INF 0x7ffffff

#define maxn 510

typedef longlong LL;

#define Min(a,b) (a<b?a:b)

#define MOD 1000000007

int m, n, Time, top, ans;

int Stack[maxn], dfn[maxn], low[maxn], blocks[maxn];

bool InStack[maxn];

typedef struct node

{

    int e, w;

    node(int e=,int w=): e(e), w(w) {}

}node;

vector<vector<node> > G;

vector<vector<node> > G2;

void init()

{

    memset(dfn, , sizeof(dfn));

    memset(low, , sizeof(low));

    ans = Time = top = ;

    G.clear();

    G.resize(n+);

    G2.clear();

    G2.resize(n+);

}

void Spfa()

{

}

void Tarjan(int u)

{

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

    Stack[top ++] = u;

    InStack[u] = true;

    int len = G[u].size();

    node v;

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

    {

        v = G[u][i];

        if( !low[v.e] )

        {

            Tarjan(v.e);

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

        }

        elseif(InStack[v.e])

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

    }

    int k;

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

    {

        do

        {

            k = Stack[--top];

            InStack[k] = false;

            blocks[k] = ans;

        }while(u != k);

        ans ++;

    }

}

int Spfa(int Star,int End)

{

    int dist[maxn];

    bool vis[maxn];

    memset(vis, false, sizeof(vis));

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

        dist[i] = INF;

    dist[Star] = ;

    queue<node> Q;

    node P, Pn;

    Q.push(node( Star,) );

    while( Q.size() )

    {

        P = Q.front();

        Q.pop();

        vis[P.e] = true;

        int len = G2[P.e].size();

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

        {

            Pn = G2[P.e][i];

            if(dist[Pn.e] > dist[P.e] + Pn.w)

            {

                dist[Pn.e] = dist[P.e] + Pn.w;

                if(!vis[Pn.e])

                    Q.push(Pn.e);

            }

        }

    }

   // for(int i=0; i<ans; i++)

     //   printf("----%d\n", dist[i]);return dist[End];

}

void solve()

{

    int k, a, b;

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

    {

        if(!low[i])

            Tarjan(i);

    }

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

    {

        int len = G[i].size();

        node v;

        for(int j=; j<len; j++)

        {

            v = G[i][j];

            a = blocks[i], b = blocks[v.e];

            if(a != b)

            {

                G2[a].push_back(node(b,v.w) );

               // printf("%d->%d,%d\n",a, b, v.w);            }

        }

    }

    scanf("%d",&k);

    while(k --)

    {

        scanf("%d %d",&a, &b);

        a = blocks[a], b = blocks[b];

        int rel = Spfa(a,b);

        if(rel == INF)

            puts("Nao e possivel entregar a carta");

        else

            printf("%d\n", rel);

    }

    printf("\n");

}

int main()

{

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

    {

        init();

        while(m--)

        {

            int a, b, c;

            scanf("%d %d %d",&a, &b, &c);

            G[a].push_back( node(b,c) );

        }

        solve();

    }

    return0;

}