记录编号	220776	评测结果	AAA
题目名称	[HAOI 2005]路由选择问题	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2016-01-20 11:44:57	内存使用	0.32 MiB

#include<cstdio>
#include<cstring>
using namespace std;
int dis[55][55];//原始输入 
int _dis[55][55]; 
int q[55];
bool inq[55];
int head,tail;
void add(int a){
	if(!inq[a]){
		inq[a]=true;
		q[tail++]=a;
		tail%=55;
	}
}
void del(){
	inq[q[head]]=false;
	head++;
	head%=55;
}
int n,s,e;
int pre[55];
void spfa(int d[][55],int flag){
	memset(q,0,sizeof(q));
	memset(inq,0,sizeof(inq));
	head = tail = 0;
	for(int i = 1;i<=n;++i){
		if(d[s][i]!=(1<<25)&&s!=i){
			add(i);
			if(flag!=0)pre[i]=s;	
		}
	}
	while(head!=tail){
		int v = q[head];
		for(int i = 1;i<=n;++i){
			if(d[s][v]+d[v][i]<d[s][i]){
				d[s][i]=d[s][v]+d[v][i];
				if(flag!=0)pre[i] = v;
				add(i);
			}
		}
		del();
	}
}
int main(){
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	scanf("%d %d %d",&n,&s,&e);
	for(int i = 1;i<=n;++i)
		for(int j = 1;j<=n;++j)
		{
			scanf("%d",&dis[i][j]);
			if(i!=j&&dis[i][j]==0)dis[i][j]=1<<25;
		}
	memcpy(_dis,dis,sizeof(dis));
	int n2;
	scanf("%d",&n2);
	for(int i = 0;i<n2;++i){
		int tmp;
		scanf("%d",&tmp);
		for(int j = 1;j<=n;++j){
			_dis[tmp][j]=_dis[j][tmp] = 1<<25;
		}
	}
	spfa(_dis,0);
	printf("%d ",_dis[s][e]);
	memcpy(_dis,dis,sizeof(dis));
	spfa(_dis,1);
	printf("%d ",_dis[s][e]);
	int mincost = _dis[s][e];
	
	int secondcost = 1<<20;
	for(int i = e;i!=s;i=pre[i]){
		memcpy(_dis,dis,sizeof(dis));
		_dis[pre[i]][i] = _dis[i][pre[i]] = 1<<25;
		spfa(_dis,0);
		if(_dis[s][e]>mincost&&_dis[s][e]<secondcost)secondcost = _dis[s][e];
		 
	} 
	printf("%d\n",secondcost);
	fclose(stdin);fclose(stdout);
	return 0;
}