POJ 3114 Countries in War - c++编程基础

3
1 3
3 1
3 2
0 0Sample Output

0
6
6
0
Nao e possivel entregar a carta

10
Nao e possivel entregar a carta
0
Source

South America 2006, Brazil Subregion
缩点最短路。
[cpp]
/***************************************************************
> File Name: countries.cpp
> Author: SDUT_GYX
> Mail: 2272902662@qq.com
> Created Time: 2013/5/29 0:16:51
**************************************************************/

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define N 260000
#define inf 0x7fffffff
using namespace std;
struct num
{
int sta,end,val,next;
}infor[N],a[N*10];
int pt[N],low[N],dfn[N],dis[N],num[N],Top,cou,id,n,m;
stack st;
bool instack[N];
int main()
{
//freopen("data1.in","r",stdin);
void Tarjan(int u);
void rebuild();
void addeage(int x,int y,int val=0);
int spfa(int sta,int end);
while(scanf("%d",&n)!=EOF)
{
if(n==0)
{
break;
}
scanf("%d",&m);
Top = 0;
memset(pt,-1,sizeof(pt));
for(int i=0;i<=m-1;i++)
{
scanf("%d %d %d",&infor[i].sta,&infor[i].end,&infor[i].val);
addeage(infor[i].sta,infor[i].end);
}
cou=id=0;
memset(instack,false,sizeof(instack));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
for(int i=1;i<=n; i++)
{
if(!dfn[i])
{
while(!st.empty())
{
st.pop();
}
Tarjan(i);
}
}
rebuild();
scanf("%d",&m);

while(m--)
{
int x,y;
scanf("%d %d",&x,&y);
int res=spfa(num[x],num[y]);
if(res==inf)
{
printf("Nao e possivel entregar a carta\n");
}else
{
printf("%d\n",res);
}
}
printf("\n");
}
}
void addeage(int x,int y,int val=0)
{
a[Top].end=y; a[Top].val =val;
a[Top].next=pt[x]; pt[x]=Top;
Top++;
}
void Tarjan(int u)
{
low[u] = dfn[u] = ++cou;
st.push(u);
instack[u] = true;
for(int i=pt[u];i!=-1; i=a[i].next)
{
int v = a[i].end;
if(!dfn[v])
{
Tarjan(v);
low[u] = min(low[u],low[v]);
}else if(instack[v])
{
low[u] = min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
int x;
id++;
do
{
x = st.top();
st.pop();
instack[x] = false;
num[x] = id;
}while(x!=u);
}
}
void rebuild()
{
memset(pt,-1,sizeof(pt));
Top = 0;
for(int i=0;i<=m-1; i++)
{
int x = infor[i].sta;
int y = infor[i].end;
int val = infor[i].val;
if(num[x]!=num[y])
{
addeage(num[x],num[y],val);
}
}
}
int spfa(int sta,int end)
{
queueque;
memset(instack,false,sizeof(instack));
for(int i=1;i<=id;i++)
{
dis[i] = inf;
}
que.push(sta);
instack[sta] = true;
dis[sta] = 0;
while(!que.empty())
{
int x = que.front();
que.po

POJ 3114 Countries in War (二)