poj3114 Countries in War 強連通縮點+最短路

http://poj.org/problem?id=3114

題意：有n個城市和m條通道，①從u城市到y城市需要w小時，②如果兩個城市互相可達屬于同一個國家，屬于同一個國家的兩個城市之間通信不需要時間。現在給出q個詢問，求u城市到v城市的最短通信時間。

題解：首先tarjan求強連通分量，然後縮點進行存圖。最後跑最短路即可，我用的是SPFA，剛好SPFA的代碼存的是鍊式前向星的闆子。

代碼：

/*
在任何深度優先搜尋中，
同一強連通分量内的所有頂點
均在同一棵深度優先搜尋樹中。
也就是說，強連通分量一定是有向圖的某個深搜樹子樹。
即dfn[x]=low[x] 
*/
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<bitset>

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>

#include<iomanip>
#include<iostream>

#define debug cout<<"aaa"<<endl
#define d(a) cout<<a<<endl
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define MIN_INT (-2147483647-1)
#define MAX_INT 2147483647
#define MAX_LL 9223372036854775807i64
#define MIN_LL (-9223372036854775807i64-1)
using namespace std;

const int N = 1000 + 5;
const int mod = 1000000000 + 7;
const double eps = 1e-8;
int n,m;
int head[N],len;
int qhead[N],qlen;
int dfn[N],low[N],dfs_num;//dfn表示周遊深度，low(u)為u或u的子樹能夠追溯到的最早的棧中節點的次序号
int color[N],col_num,num[N];//染色 
int stack[N],vis[N],top;//棧和棧指針
int dis[N];

struct EdgeNode{
	int from,to,next,w;
}edge[N*N],qedge[N*N];

void qadd(int i,int j,int w){
	qedge[qlen].from=i;
	qedge[qlen].to=j;
	qedge[qlen].w=w;
	qedge[qlen].next=qhead[i];
	qhead[i]=qlen++;
}

void add(int i,int j,int w){
	edge[len].from=i;
	edge[len].to=j;
	edge[len].w=w;
	edge[len].next=head[i];
	head[i]=len++;
} 

void init(){
	mem(color,0),mem(vis,0),mem(dfn,0),mem(low,0),mem(qhead,-1),mem(head,-1),qlen=len=top=col_num=dfs_num=0;
}

void tarjan(int x){
	dfn[x]=low[x]=++dfs_num;
	vis[x]=1;//是否在棧中
	stack[++top]=x;
	for(int i=head[x];i!=-1;i=edge[i].next){
		int temp=edge[i].to;
		if(!dfn[temp]){
			tarjan(temp);
			low[x]=min(low[x],low[temp]);
		}
		else if(vis[temp]){
			low[x]=min(dfn[temp],low[x]);
		}
	} 
	if(dfn[x]==low[x]){//構成強連通分量 
		vis[x]=0;
		//染色 
		color[x]=++col_num;
		num[col_num]=1;
		while(stack[top]!=x){//退棧 
			color[stack[top]]=col_num;
			num[col_num]++;
			vis[stack[top]]=0;
			top--; 
		}
		top--;
	}
}

bool SPFA(int s,int n){
	//vis标記是否在隊列中 
	mem(vis,0);
	for(int i=0;i<=n;i++){
		dis[i]=MAX_INT;
	}
	dis[s]=0;
	queue<int> q;
	q.push(s);vis[s]=1;
	while(!q.empty()){
		//隊頭元素出隊，并且消除标記 
		int x=q.front();q.pop();vis[x]=0;
		for(int k=qhead[x];k!=-1;k=qedge[k].next){
			int y=qedge[k].to;
			if(dis[x]+qedge[k].w<dis[y]){
				dis[y]=dis[x]+qedge[k].w;//松弛
				if(!vis[y]){//點y不在隊内 
					vis[y]=1;//标記 
					q.push(y);
				} 
			}
		} 
	}
	return 1; 
}

void solve(){
	int u,v,q;
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int k=head[i];k!=-1;k=edge[k].next){
			u=color[edge[k].from],v=color[edge[k].to];
			if(u!=v){
				qadd(u,v,edge[k].w);
			}
		}
	}
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&u,&v);
		u=color[u],v=color[v];
		SPFA(u,n);
		if(dis[v]<MAX_INT){
			printf("%d\n",dis[v]);
		}
		else{
			puts("Nao e possivel entregar a carta");
		}
	}
	puts("");
}

int main(){
	int u,v,w;
	while(~scanf("%d%d",&n,&m)){
		if(n==0&&m==0) break;
		init();
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);
		}
		solve();
	}
	return 0;
}