poj 3114 Countries in War（强连通缩点+最短路）

思路：Tarjan缩点+SPFA最短路。

#include<cstdio>#include<queue>#include<cstring>#include<iostream>#include<algorithm>#define debuusing  namespace std;const int maxn=500+50;const int maxm=250000+50;const int INF=0x3f3f3f3f;struct Node{    int u,v,w;    Node(int u=0,int v=0,int w=0):u(u),v(v),w(w) {}};struct Edge{    int to,w,next;};int s[100000+50];Node e[maxm];int vis[maxn],sc[maxn];int v[maxn],dist[maxn];int dfn[maxn],low[maxn];int all,n,m,tot,top,cnt,q,tot2;int head[maxm],head2[maxm];Edge edge[maxm],edge2[maxm];void addEdge(int u,int v,int w){    edge[tot].to=v,edge[tot].next=head[u];    edge[tot].w=w,head[u]=tot++;}void addEdge2(int u,int v,int w){    edge2[tot2].to=v,edge2[tot2].next=head2[u];    edge2[tot2].w=w,head2[u]=tot2++;}void Tarjan(int u){    all++,dfn[u]=low[u]=all;    top++,s[top]=u,vis[u]=1;    for(int i=head[u]; ~i; i=edge[i].next)    {        int nt=edge[i].to;        if(!dfn[nt])        {            Tarjan(nt);            low[u]=min(low[u],low[nt]);        }        else        {            if(vis[nt])                low[u]=min(low[u],dfn[nt]);        }    }    if(low[u]==dfn[u])    {        cnt++;        while(s[top+1]!=u)        {            sc[s[top]]=cnt;            vis[s[top]]=0;            top--;        }    }}void init(){    all=tot=top=cnt=tot2=0;    memset(s,0,sizeof(s));    memset(sc,0,sizeof(sc));    memset(vis,0,sizeof(vis));    memset(dfn,0,sizeof(dfn));    memset(low,0,sizeof(low));    memset(head,-1,sizeof(head));    memset(head2,-1,sizeof(head2));}void SPFA(int s){    queue<int> q;    memset(v,0,sizeof(v));    for(int i=1; i<=n; i++) dist[i]=INF;    v[s]=1,q.push(s),dist[s]=0;    while(!q.empty())    {        int now=q.front();        q.pop(),v[now]=0;        for(int i=head2[now]; ~i; i=edge2[i].next)        {            int nt=edge2[i].to;            if(dist[nt]>dist[now]+edge2[i].w)            {                dist[nt]=dist[now]+edge2[i].w;                if(!v[nt])                {                    v[nt]=1;                    q.push(nt);                }            }        }    }}int main(){#ifdef debug    freopen("in.in","r",stdin);#endif // debug    while(scanf("%d%d",&n,&m)!=EOF&&n)    {        init();        for(int i=0; i<m; i++)        {            int x,y,w;            scanf("%d%d%d",&x,&y,&w);            addEdge(x,y,w);            e[i]=Node(x,y,w);        }        for(int i=1; i<=n; i++)            if(!dfn[i]) Tarjan(i);        for(int i=0; i<m; i++)        {            int x=sc[e[i].u],y=sc[e[i].v];            if(x!=y) addEdge2(x,y,e[i].w);        }        scanf("%d",&q);        for(int i=0; i<q; i++)        {            int x,y,xx,yy;            scanf("%d%d",&x,&y);            xx=sc[x],yy=sc[y];            if(xx==yy) printf("0/n");            else            {                SPFA(xx);                if(dist[yy]>=INF) printf("Nao e possivel entregar a carta/n");                else printf("%d/n",dist[yy]);            }        }        printf("/n");    }    return 0;}