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

(相关资料图)

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

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

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

#include#include#include#include#includeusing 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 &arr) {    memset(vis, 0, sizeof(vis));    memset(dis, 0x3f3f3f3f, sizeof(dis));    queue 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 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 arr(n);        for (int i = 0; i < n; i++) cin >> arr[i];        if (spfa(arr)) cout << "Yes\n";        else cout << "No\n";    }    return 0;}

关键词：