记录编号	57094	评测结果	AAA
题目名称	[HAOI 2005]路由选择问题	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2013-04-06 10:19:17	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
#include<iomanip>
using namespace std;
const int SIZEN=60;
const int INF=0xffffff;
int s,t;
int n;
int c_complete[SIZEN][SIZEN]={0};//正常的邻接矩阵
int c_damaged[SIZEN][SIZEN]={0};//考虑故障后的邻接矩阵
int c_temp[SIZEN][SIZEN]={0};//打酱油的邻接矩阵
int p;//故障节点个数
int fault[SIZEN]={0};//故障节点编号
int father[SIZEN];
deque<int> path;
//注意:节点下标是1~n
int Dijkstra(int c[SIZEN][SIZEN],bool flag,int father[SIZEN]){
	int f[SIZEN]={0};
	bool used[SIZEN]={0};
	int i,sum=1,min=-1;
	for(i=1;i<=n;i++) if(i!=s) f[i]=INF;
	while(sum<n){
		min=-1;
		for(i=1;i<=n;i++){
			if(used[i]) continue;
			if(min==-1||f[i]<f[min]) min=i;
		}//找到扩展的节点
		used[min]=true,sum++;
		if(min==-1) break;
		for(i=1;i<=n;i++){
			if(used[i]) continue;
			if(f[min]+c[min][i]<f[i]){//relax
				f[i]=f[min]+c[min][i];
				if(flag) father[i]=min;
			}
		}
	}
	return f[t];
}
void read(void){
	scanf("%d%d%d",&n,&s,&t);
	int i,j;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			scanf("%d",&c_complete[i][j]);
			if(i!=j&&!c_complete[i][j]) c_complete[i][j]=INF;
		}
	}
	scanf("%d",&p);
	for(i=1;i<=n;i++) scanf("%d",&fault[i]);
}
void damage(int x,int c[SIZEN][SIZEN]){
	int i;
	for(i=1;i<=n;i++){
		if(i!=x) c[x][i]=c[i][x]=INF;
	}
}
void search_path(void){
	int temp=t;
	while(temp!=s){
		path.push_front(temp);
		temp=father[temp];
	}
	path.push_front(s);
}
void assign(int c1[SIZEN][SIZEN],int c2[SIZEN][SIZEN]){//c1给c2赋值
	int i,j;
	for(i=1;i<=n;i++) for(j=1;j<=n;j++) c2[i][j]=c1[i][j];
}
void work(void){
	int i;
	assign(c_complete,c_damaged);
	for(i=1;i<=p;i++) damage(fault[i],c_damaged);
	printf("%d ",Dijkstra(c_damaged,0,father));
	printf("%d ",Dijkstra(c_complete,1,father));//不考虑节点的最短路
	search_path();
	assign(c_complete,c_temp);
	int ans=INF,temp;
	for(i=1;i<path.size();i++){
		temp=c_complete[path[i-1]][path[i]];
		c_temp[path[i-1]][path[i]]=INF;
		ans=min(ans,Dijkstra(c_temp,0,father));
		c_temp[path[i-1]][path[i]]=temp;
	}
	printf("%d\n",ans);
}
int main(){
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	read();
	work();
	return 0;
}