记录编号	83369	评测结果	AAA
题目名称	[HAOI 2005]路由选择问题	最终得分	100
用户昵称	Frost	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2013-12-02 20:14:55	内存使用	0.33 MiB

#include<iostream>
#include<fstream>
#define intmax 20000;
#include<cstring>
#include<algorithm>
using namespace std;
int map[51][51],dist[51],n,mi;
int start,end;
struct node
{
	int head;
};
node path[51];
void spfa(int s)
{
	int h=0,t=1;
	int v[51],q[51];
	for(int i=1;i<=n;++i)
	{
		dist[i]=intmax;
	}
	memset(q,0,sizeof(q));
	memset(v,0,sizeof(v));
	dist[s]=0;
	v[s]=1;
	q[t]=s;
	while(h!=t)
	{
		h=(h+1)%(n+1);
		int x=q[h];
		v[x]=0;
		for(int i=1;i<=n;++i)
		{
			if(dist[i]>dist[x]+map[x][i]&&map[x][i]!=0)
			{
				path[i].head=x;
				dist[i]=dist[x]+map[x][i];
				if(!v[i])
				{
					t=(t+1)%(n+1);
					q[t]=i;
					v[i]=1;
				}
			}
		}
	}
}
void dfs(int x)
{
	int b,c;
	if(x!=start)
	{
		b=path[x].head;
		c=map[x][b];
		map[x][b]=0;
		map[b][x]=0;
		spfa(start);
		map[x][b]=c;
		map[b][x]=c;
		mi=min(dist[end],mi);
		dfs(b);
	}
}
		
void printpath(int x)
{
	int b;
	if(x!=start)
	{
		b=path[x].head;
		printpath(b);
		cout<<b<<"->";
	}
}
int main()
{
	ifstream in("route.in");
	ofstream out("route.out");
	in>>n>>start>>end;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			int c;
			in>>c;
			map[i][j]=c;
			map[j][i]=c;
		}
	}
	int m;
	in>>m;
	int x[m+1];
	for(int i=1;i<=m;++i)
	{
		in>>x[i];
	}
	spfa(start);
	int s1=dist[end];
	mi=intmax;
	dfs(end);
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=n;++j)
		{
			map[j][x[i]]=0;
			map[x[i]][j]=0;
		}
	}
	spfa(start);
	out<<dist[end]<<" "<<s1<<" "<<mi<<endl;
	return 0;
}