题目链接：
?id=3114
题目大意：
间谍在战争期间想要传递一份谍报回国，谍报可以在邮局之间传递，但这种传递是单向的，
并且会小号一些时间。但是如果两个邮局在同一个国家的话，那么谍报在这两个邮局之间传
递是不消耗时间的，可以立即到达。如果几个邮局发出的谍报可以通过一些路径相互到达，
那么这些邮局就属于一个国家。那么问题来了：给出一个起点和终点，问最快什么时候能够
将谍报传递到。
思路：
本题求得是有向图上的最短路。以邮局为点，从一个邮局到达另一个邮局的时间为边权，但是
这里的边权分两组：相同国家的邮局之间的边权和不同国家的邮局之间的边权。考虑到相同国
家之间的邮局直接可以相互到达。所以想到了强连通分量。可以相互达到的邮局其实就是一个
强连通分量，将原图进行缩点。那么一个强连通分量就是一个国家。
进行缩点之后，原图就变成了一个有向无环图(DAG)，重新建图，然后根据输入的起点和终点，
对新图用SPFA算法求最短路径。这道题和POJ3592一样，，详细参考博文：
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int MAXN = 550;const int MAXM = MAXN*MAXN;const int INF = 0xffffff0;struct EdgeNode{int to;int w;int next;}Edges[MAXM],Edges1[MAXM];int Head[MAXN],Head1[MAXN];int low[MAXN],dfn[MAXN],belong[MAXN];int vis[MAXN],vist[MAXN];int Stack[MAXN];int m,lay,scc,id,ip,N,M;int Dist[MAXN];void AddEdges(int u,int v,int w){Edges[id].to = v;Edges[id].w = w;Edges[id].next = Head[u];Head[u] = id++;}void AddEdges1(int u,int v,int w){Edges1[ip].to = v;Edges1[ip].w = w;Edges1[ip].next = Head1[u];Head1[u] = ip++;}int TarBFS(int pos){int v;vis[pos] = 1;low[pos] = dfn[pos] = ++lay;Stack[m++] = pos;for(int i = Head[pos]; i != -1; i = Edges[i].next){int v = Edges[i].to;if( !dfn[v] ){TarBFS(v);low[pos] = min(low[pos],low[v]);}else if(vis[v])low[pos] = min(low[pos],low[v]);}if(dfn[pos] == low[pos]){++scc;do{v = Stack[–m];belong[v] = scc;vis[v] = 0;}while(v != pos);}return 0;}void ReBuildMap(){for(int u = 1; u <= N; ++u){for(int k = Head[u]; k != -1; k = Edges[k].next){int v = Edges[k].to;if(belong[u] != belong[v])AddEdges1(belong[u],belong[v],Edges[k].w);}}}void SPFA(int s){memset(vist,0,sizeof(vist));for(int i = 0; i <= N; ++i) //不能用memset(Dist,INF,sizeof(Dist));赋值Dist[i] = INF;queue<int> Q;Q.push(s);vist[s] = 1;Dist[s] = 0;while( !Q.empty() ){int u = Q.front();Q.pop();vist[u] = 0;for(int i = Head1[u]; i != -1; i = Edges1[i].next){int v = Edges1[i].to;if(Dist[v] > Dist[u] + Edges1[i].w){Dist[v] = Dist[u] + Edges1[i].w;if( !vist[v] ){vist[v] = 1;Q.push(v);}}}}}int main(){int u,v,w,k;while(~scanf("%d%d",&N,&M) && N){memset(Head,-1,sizeof(Head));memset(Head1,-1,sizeof(Head1));memset(vis,0,sizeof(vis));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));scc = m = lay = id = ip = 0;for(int i = 0; i < M; ++i){scanf("%d%d%d",&u,&v,&w);AddEdges(u,v,w);}for(int i = 1; i <= N; ++i){if(!dfn[i])TarBFS(i);}ReBuildMap();scanf("%d",&k);while(k–){scanf("%d%d",&u,&v);if(belong[u]==belong[v])printf("0\n");else{SPFA(belong[u]);if(Dist[belong[v]] != INF)printf("%d\n",Dist[belong[v]]);elseprintf("Nao e possivel entregar a carta\n");}}printf("\n");}return 0;}
希望你灰暗的心情在此刻明亮起来，去迎接美好的明天!
