http://poj.org/problem?id=3114
缩点+DIJK 注意缩点之后有重边啊 floyd会TLE
#include <iostream>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
#include<algorithm>
#include<stack>
#define N 510
#define M 301000
#define INF 0xfffffff
using namespace std;
struct node
{
int u,v,next,w;
}edge[M];
int t,low[N],pre[N],sccno[N],head[N],scc,dep,ww[N][N],vis[N],dis[N];
int o[N][N];
void init()
{
t = ;
memset(head,-,sizeof(head));
}
void add(int u,int v,int w)
{
edge[t].u =u;
edge[t].v = v;
edge[t].w = w;
edge[t].next = head[u];
head[u] = t++;
}
stack<int>s;
void dfs(int u)
{
low[u] = pre[u] = ++dep;
s.push(u);
for(int i = head[u] ; i!=- ; i = edge[i].next)
{
int v = edge[i].v;
if(!pre[v])
{
dfs(v);
low[u] = min(low[u],low[v]);
}
else if(!sccno[v])
low[u] = min(low[u],pre[v]);
}
if(low[u]==pre[u])
{
scc++;
for(;;)
{
int x = s.top();s.pop();
sccno[x] = scc;
if(x==u)break;
}
}
}
void find_scc(int n)
{
scc=;dep=;
memset(low,,sizeof(low));
memset(pre,,sizeof(pre));
memset(sccno,,sizeof(sccno));
for(int i = ; i <= n ; i++)
if(!pre[i])
dfs(i);
}
int dijk(int st,int en,int n)
{
int i,j,k,mi;
memset(vis,,sizeof(vis));
for(i = ; i <= n ; i++)
dis[i] = o[st][i];
dis[st] = ;
for(i = ;i <= n ; i++)
{
mi = INF;
for(j = ; j <= n ; j++)
if(!vis[j]&&dis[j]<=mi)
mi = dis[k=j];
vis[k] = ;
for(j = ; j <= n ; j++)
if(dis[j]>o[k][j]+dis[k])
dis[j] = o[k][j]+dis[k];
}
return dis[en];
}
int main()
{
int i,j,n,m,k,a,b,c,g;
while(cin>>n>>m)
{
if(n==&&m==)
break;
memset(ww,,sizeof(ww));
init();
for(i =; i <= m ;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
find_scc(n);
for(i = ; i <= n ; i++)
for(j = ; j <= n ;j++)
o[i][j] = INF;
for(i = ; i <= scc ; i++)
o[i][i] = ;
for(i = ; i < t ; i++)
{
int u = edge[i].u,v = edge[i].v;
if(sccno[u]!=sccno[v])
{
o[sccno[u]][sccno[v]] = min(o[sccno[u]][sccno[v]],edge[i].w);//没算重的之前 WA惨了
}
}
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&a,&b);
int xx = dijk(sccno[a],sccno[b],scc);
if(xx==INF)
printf("Nao e possivel entregar a carta\n");
else
cout<<xx<<endl;
}
puts("");
}
return ;
}