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;
}