记录编号	131534	评测结果	AAA
题目名称	[HAOI 2005]路由选择问题	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2014-10-24 17:00:44	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
queue<int> A;
bool pan[51]={0},qwq;
int n,to[51][51]={0},street[51][51]={0},zui[51]={0},rezui[51][2]={0},cofr[51]={0},i,j,zj1,zj2,zj3,p,fr,en,s0,s1,s2;
void init()
{
	scanf("%d%d%d",&n,&fr,&en);
	for(i=1;i<=n;i++)
	for(p=1;p<=n;p++)
	{
		scanf("%d",&zj1);
		if(zj1)
		{
			to[i][0]++;
			to[i][ to[i][0] ]=p;
			street[i][p]=zj1;
		}
	}
	scanf("%d",&zj2);
	for(i=1;i<=zj2;i++)
	{
		scanf("%d",&zj1);
		pan[zj1]=true;
	}
}
void s0work()
{
	for(i=1;i<=n;i++)zui[i]=0x7fffffff;
	zui[fr]=0;
	for(i=1;i<=to[fr][0];i++)
	if(!pan[ to[fr][i] ])
	{
		A.push(to[fr][i]);
		zui[ to[fr][i] ]=street[fr][ to[fr][i] ];
	}
	while(!A.empty())
	{
		zj1=A.front();A.pop();
		for(i=1;i<=to[zj1][0];i++)
		if(!pan[ to[zj1][i] ])
		{
			zj2=zui[zj1]+street[zj1][ to[zj1][i] ];
			if(zj2<zui[ to[zj1][i] ])
			{
				zui[ to[zj1][i] ]=zj2;
				A.push(to[zj1][i]);
			}
		}
	}
	s0=zui[en];
}
void s1ands2work()
{
	for(i=1;i<=n;i++)rezui[i][0]=rezui[i][1]=1000000;
	rezui[fr][1]=0;
	A.push(fr);
	while(!A.empty())
	{
		zj1=A.front();A.pop();
		for(i=1;i<=to[zj1][0];i++)
		{
			qwq=false;
			zj2=rezui[zj1][1]+street[zj1][ to[zj1][i] ];
			zj3=rezui[zj1][0]+street[zj1][ to[zj1][i] ];
			if(zj2<rezui[ to[zj1][i] ][1])
			{
				rezui[ to[zj1][i] ][0]=rezui[ to[zj1][i] ][1];//更新第二小的值 
				rezui[ to[zj1][i] ][1]=zj2;//更新最小值 
				cofr[ to[zj1][i] ]=zj1;//记录转移点 
				if(zj3<rezui[ to[zj1][i] ][0]) rezui[ to[zj1][i] ][0]=zj3;
				qwq=true;
			}
			else//第二小的更新 
			if(zj2<rezui[ to[zj1][i] ][0]&&cofr[ to[zj1][i] ]!=zj1)
			{
				rezui[ to[zj1][i] ][0]=zj2;
				qwq=true;
			}
			if(qwq)//假如更新过，则此点入队
			A.push(to[zj1][i]); 
		}
	}
	s1=rezui[en][1];
	s2=rezui[en][0];
}
int main()
{
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	init();
	s0work();
	s1ands2work();
	printf("%d %d %d\n",s0,s1,s2);
	return 0;
}