poj -- 3114 Countries in War（強連通+最短路）

題目大意：間諜在戰争期間想要傳遞一份郵件回國，郵件可以在各個郵局之間傳播，但傳遞是單向耗時的；如果兩個郵局在同一個國家時，那麼郵件在他們之間傳遞是不費時的；判斷兩個郵局在同一個國家的标準是兩個郵局之間可以互相傳遞郵件；給定一個起點終點，問傳遞郵件的最短時間；

思路分析：求強連通分量縮點後，對于一個起點終點，如果在一個強連通分量中時，直接輸出0，否則用Dijkstra求最短路；

代碼實作：

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<iostream>
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define MEM(a) (memset((a),0,sizeof(a)))
#define MEME(a) (memset((a),-1,sizeof(a)))
#define MEMX(a) (memset((a),0x3f,sizeof(a)))
using namespace std;
const int N=510;
int dfn[N],low[N],st[N],belong[N],dis[N],bcnt,tim,top,s_top,top1,n,m;
bool inst[N],vis[N];
struct Edge{
    int v1,va;
    Edge *next;
    Edge(int _v1=0,int _va=0,Edge *_next=0):v1(_v1),va(_va),next(_next){}
}*head[N],*h[N],e[N*N];
struct node{
    int v1,va;
    node(int _v1=0,int _va=0):v1(_v1),va(_va){}
    bool operator<(const node& rhs)const {
        return va>rhs.va;
    }
};
vector<node> v[N];
void Addedge(int from,int to,int val){
    Edge *p=&e[top++];
    p->v1=to;
    p->va=val;
    p->next=head[from];
    head[from]=p;
}
void Tarjan(int i){
    dfn[i]=low[i]=++tim;
    st[++s_top]=i;
    inst[i]=1;
    int to;
    for(Edge *p=head[i];p;p=p->next){
        to=p->v1;
        if(!dfn[to]){
            Tarjan(to);
            if(low[to]<low[i]) low[i]=low[to];
        }else if(inst[to]&&dfn[to]<low[i]) low[i]=dfn[to];
    }
    if(dfn[i]==low[i]){
        bcnt++;
        do{
            to=st[s_top--];
            inst[to]=0;
            belong[to]=bcnt;
        }while(i!=to);
    }
}
int Dijkstra(int o,int d){
    priority_queue<node> q;
    MEMX(dis),MEM(vis);
    dis[o]=0;
    q.push(node(o,0));
    int head,now_v1,now_va;
    while(!q.empty()){
        head=q.top().v1;
        if(head==d) return q.top().va;
        q.pop();
        vis[head]=1;
        for(int i=0;i<v[head].size();++i){
            now_v1=v[head][i].v1,now_va=v[head][i].va;
            if(!vis[now_v1]&&dis[head]+now_va<dis[now_v1]){
                dis[now_v1]=dis[head]+now_va;
                q.push(node(now_v1,dis[now_v1]));
            }
        }
    }
    return -1;
}
int main(){
    int x,y,hour,k,o,d;
    while(~scanf("%d",&n),n){
        scanf("%d",&m);
        MEM(head),MEM(h),MEM(dfn),MEM(low),MEM(inst);
        for(int i=1;i<=n;++i) v[i].clear();
        bcnt=top=top1=s_top=tim=0;
        node tmp;
        while(m--){
            scanf("%d%d%d",&x,&y,&hour);
            Addedge(x,y,hour);
        }
        for(int i=1;i<=n;++i) if(!dfn[i]) Tarjan(i);
        for(int i=1;i<=n;++i)
            for(Edge *p=head[i];p;p=p->next)
                if(belong[i]!=belong[p->v1]){
                    tmp.v1=belong[p->v1],tmp.va=p->va;
                    v[belong[i]].push_back(tmp);
                }
        scanf("%d",&k);
        while(k--){
            scanf("%d%d",&o,&d);
            if(belong[o]==belong[d]){
                printf("0\n");
                continue;
            }
            int ans=Dijkstra(belong[o],belong[d]);
            if(ans!=-1) printf("%d\n",ans);
            else printf("Nao e possivel entregar a carta\n");
        }
        printf("\n");
    }
}