记录编号	577516	评测结果	AAA
题目名称	[HAOI 2005]路由选择问题	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-11-07 22:13:53	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, p, st, to, g[2][100][100], ans, num;
vector<int> cd[100], w[100];
bool vis[100], ok[100];
void dfs(int x, int s) {
	if(x == to) {
		if(s != g[1][st][to]) {
			ans = min(ans, s);
		}
		return ;
	}
	if(s >= ans) {
		return ;
	}
	for(int i = 0; i < cd[x].size(); i ++) {
		int u = cd[x][i];
		if(!vis[u]) {
			vis[u] = 1;
			dfs(u, s + w[x][i]);
			vis[u] = 0;
		}
	}
}
signed main() {
	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);
	cin >> n >> st >> to;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= n; j ++) {
			cin >> g[0][i][j];
			if(!g[0][i][j]) {
				g[0][i][j] = 0x3f3f3f3f;
			}
			else {
				cd[i].push_back(j);
				w[i].push_back(g[0][i][j]);
			}
			g[1][i][j] = g[0][i][j];
		}
	}
	cin >> p;
	for(int i = 1; i <= p; i ++) {
		int x;
		cin >> x;
		ok[x] = 1;
	}
	for(int i = 1; i <= n; i ++) {
		g[0][i][i] = g[1][i][i] = 0;
	}
	for(int k = 1; k <= n; k ++) {
		for(int i = 1; i <= n; i ++) {
			for(int j = 1; j <= n; j ++) {
				if(!ok[i] && !ok[j] && !ok[k]) {
					g[0][i][j] = min(g[0][i][j], g[0][i][k] + g[0][k][j]);
				}
				g[1][i][j] = min(g[1][i][j], g[1][i][k] + g[1][k][j]);
			}
		}
	}
	ans = 1e8;
	vis[st] = 1;
	dfs(st, 0);
	cout << g[0][st][to] << ' ' << g[1][st][to] << ' ' << ans << endl;
	return 0;
}