PAT题目链接：https://pintia.cn/problem-sets/994805342720868352/exam/problems/1478635670373253120
这题踩了太多坑，本来没什么内容，硬是断断续续查了三天的bug：
第一天： 循环的时候内部判断逻辑不要写在for循环里，否则本该continue的逻辑，硬生生变成了break。我真是脑袋瓜秀逗了才会这么写代码。
第二天： 混淆了dijkstra和一般最短路算法的思想，导致迟迟得不到想要的结果。最后参考了层序遍历的思想，改掉了这个bug。
第三天： 题目说Ne不超过105，但是开边的时候数组要开205, 因为是双向的。最后那个段错误又卡了我好久。
#include<iostream>
#include<queue>
#include<vector>
#include<set>
#include<cstring>
using namespace std;
int n, m, k;
struct edge {
int to, next, c;
} g[200005];
int head[1005], dis[1005], vis[1005], cnt;
inline void add(int a, int b, int c) {
g[++cnt] = edge{b, head[a], c};
head[a] = cnt;
}
bool spfa(vector<int> &arr) {
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f3f3f3f, sizeof(dis));
queue<int> q;
int idx = 0;
q.push(arr[idx++]);
dis[arr[0]] = 0;
vis[arr[0]] = 1;
while (q.size()) {
// 灵感来源——层序遍历
int size = q.size();
// 上一波出队, 更新状态
for (int j = 0; j < size; j++) {
int ind = q.front(); q.pop();
for (int i = head[ind]; i; i = g[i].next) {
int to = g[i].to, c = g[i].c;
if (dis[ind] + c < dis[to]) dis[to] = dis[ind] + c;
}
}
// 下一波入队
int min_dis = 0x3f3f3f3f;
set<int> v;
for (int to = 1; to <= n; to++) {
if (to == arr[0]) continue;
if (!vis[to]) {
if (dis[to] < min_dis) {
min_dis = dis[to];
v.clear();
v.insert(to);
} else if (dis[to] == min_dis) {
v.insert(to);
}
}
}
while (v.size()) {
if (v.find(arr[idx]) != v.end()) {
q.push(arr[idx]); vis[arr[idx]] = 1;
v.erase(arr[idx]);
idx++;
} else {
return false;
}
}
}
return idx == n;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
cin >> k;
while (k--) {
vector<int> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];
if (spfa(arr)) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}