http://poj.org/problem?id=3114
题目大意：
n个间谍 他们之间传送信息需要一定的时间
一个联通分量里面的间谍属于一个国家，之间的信息传递不需要时间
然后问你从一个间谍传一个信息到另一个间谍那需要最少时间 也可能传不到
联通缩点+最短路
缩点所得到的新图 可能是因为有重边或是太稠密 用邻接表容易超时
基本步骤：
1，输入去重边
2，Tarjan缩点
3，重新调整缩点后间谍之间的信息传递时间
4，最短路
注意： 图有可能不完全连通
代码及其注释：
#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
const int M=1000000002;
const int N=515;
struct node
{
struct tt *next;
}mem[N];
struct node1
{
struct tt *next;
}remem[N];
struct tt
{
struct tt *next;
int j;
};
bool in[N];
bool visited[N];
int deep;
stack<int>str;
int dfn[N];
int low[N];
int uppoint[N];
int time[N][N];
inline void build(int i,int j)
{
struct tt *t=new tt;
t->j=j;
t->next=mem[i].next;
mem[i].next=t;
}
inline void Clearlist(int n)
{
for(int i=1;i<=n;++i)
{
mem[i].next=NULL;
}
}
void Tarjan(int x)//缩点
{
++deep;
dfn[x]=low[x]=deep;
visited[x]=true;
in[x]=true;
str.push(x);
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(visited[t->j]==false)
{
Tarjan(t->j);
low[x]=min(low[x],low[t->j]);
}else if(in[t->j]==true)
{
low[x]=min(low[x],dfn[t->j]);
}
t=t->next;
}
if(low[x]==dfn[x])
{
while(str.top()!=x)
{
uppoint[str.top()]=x;
in[str.top()]=false;
str.pop();
}
uppoint[str.top()]=x;
in[str.top()]=false;
str.pop();
}
}
void dfs(int x)//调整缩点后有用点之间的信息传递时间
{
visited[x]=true;
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(uppoint[x]!=uppoint[t->j])
{
time[uppoint[x]][uppoint[t->j]]=min(time[uppoint[x]][uppoint[t->j]],time[x][t->j]);
}
if(!visited[t->j])
{
dfs(t->j);
}
t=t->next;
}
}
int mintime(int st,int nd,int n)//求最短路
{
if(st==nd)
return 0;
int dist[N];
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;++i)
if(time[st][i]==-1)
dist[i]=M;
else
dist[i]=time[st][i];
visited[st]=true;
for(int w=1;w<n;++w)
{
int MIN=M;int k=-1;
for(int i=1;i<=n;++i)
{
if(!visited[i]&&dist[i]<MIN)
{
MIN=dist[i];k=i;
}
}
if(k==-1)
break;
if(k==nd)
break;
visited[k]=true;
for(int i=1;i<=n;++i)
{
if(dist[i]>dist[k]+time[k][i])
dist[i]=dist[k]+time[k][i];
}
}
return dist[nd];
}
int main()
{
int n,m,q;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
for(int i=1;i<=n;++i)//初始化
{
for(int j=i;j<=n;++j)
time[i][j]=time[j][i]=M;
}
while(m--)
{
int i,j,k;
scanf("%d %d %d",&i,&j,&k);
if(time[i][j]>k)//去重边
time[i][j]=k;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(time[i][j]!=M)//建原图
build(i,j);
}
}
memset(dfn,-1,sizeof(dfn));
memset(visited,false,sizeof(visited));
memset(in,false,sizeof(in));
memset(uppoint,-1,sizeof(uppoint));
while(!str.empty())
str.pop();
deep=0;
for(int i=1;i<=n;++i)
{
if(dfn[i]==-1)//因为图有可能不完全联通
Tarjan(i);
}
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;++i)
{
if(!visited[i])//因为图有可能不完全联通
{
dfs(i);
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(i!=uppoint[i]||j!=uppoint[j])//处理一下非联通缩点之间的信息传递时间
time[i][j]=M;
}
}
scanf("%d",&q);
while(q--)
{
int i,j,k;
scanf("%d %d",&i,&j);
i=uppoint[i];j=uppoint[j];
k=mintime(i,j,n);
if(k==M)
printf("Nao e possivel entregar a carta\n");
else
printf("%d\n",k);
}
printf("\n");
Clearlist(n);
}
return 0;
}
