题解

一开始没读题就0帧起手，写了个bfs找环+Floyd算法.

直到我看到了：不会重复经过同一个车站.

天塌了70+行的代码白写了

但是这个提示也带给我了一个好消息：消耗的时间最多也不会超过 $15$.

这就让我想到了最短Hamilton路径的解法：状压DP.

巧了，在这题也同样适用！

我们弄个dp，$dp[i][j][k]$ 表示从 $i$ 出发，第 $k$ 个状态，最后一个点为 $j$ 是否可能实现.

然后枚举每个时间和所有点，判断当时间为 $i$，选取 $j$ 点作为车站是否可行.

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int a[20];
bool edge[20][20];
bool dp[15][15][32768];
vector <int> v[16];
int n, m, k;
//15？肢解暴力！ 
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	cin >> n >> m >> k;
	for(int i = 0; i < k; i++) cin >> a[i], a[i]--;//由于状压DP需要以0作为起始点，所以要-1 
	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		edge[x - 1][y - 1] = edge[y - 1][x - 1] = 1;//同理
	}
	for(int i = 0; i < n; i++){//遍历所有点 
		dp[i][i][1 << i] = 1;
		for(int tmp = (1 << i) + 1; tmp < (1 << n); tmp++){//遍历每一个状态
			for(int j = 0; j < n; j++){
				if(tmp >> j & 1){//这个状态是否包括这个点
					for(int k = 0; k < n; k++){
						if((tmp >> k & 1) && edge[j][k]){//这个状态是否包括这个点，这两个点是否可达
							dp[i][k][tmp] = (dp[i][k][tmp] || dp[i][j][tmp - (1 << k)]);//更新，之前的经历告诉我逻辑或比按位或更快
						}
					}
				}
			}
		}
	}
	for(int i = 0; i < (1 << n); i++){
		v[__builtin_popcount(i)].push_back(i);//记录当前状态所需的时间
	}
	
	for(int times = 0; times <= n; times++){//选时间 
		for(int tmp = 0; tmp < n; tmp++){//挑车站 
			bool flag = 1;
			for(int i = 0; i < k; i++){//看看人 
				bool flag2 = 0;
				for(int j:v[times]){
					if(dp[a[i]][tmp][j]){
						flag2 = 1;
						break;
					}
				}
				if(!flag2){flag = 0; break;}
			}
			if(flag){cout << tmp + 1; return 0;}
		}
	}
	
	cout << -1;

	return 0;
}

时间复杂度：$O(2^N\times N^3)$.