1163 Dijkstra Sequence + 层序遍历 + 链式前向星

PAT题目链接：https://pintia.cn/problem-sets/994805342720868352/exam/problems/1478635670373253120

这题踩了太多坑，本来没什么内容，硬是断断续续查了三天的bug：

第一天： 循环的时候内部判断逻辑不要写在for循环里，否则本该continue的逻辑，硬生生变成了break。我真是脑袋瓜秀逗了才会这么写代码。
第二天： 混淆了dijkstra和一般最短路算法的思想，导致迟迟得不到想要的结果。最后参考了层序遍历的思想，改掉了这个bug。
第三天： 题目说Ne不超过10⁵，但是开边的时候数组要开20⁵, 因为是双向的。最后那个段错误又卡了我好久。

#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;
}