(相關(guān)資料圖)

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

這題踩了太多坑，本來沒什么內(nèi)容，硬是斷斷續(xù)續(xù)查了三天的bug：

第一天： 循環(huán)的時候內(nèi)部判斷邏輯不要寫在for循環(huán)里，否則本該continue的邏輯，硬生生變成了break。我真是腦袋瓜秀逗了才會這么寫代碼。第二天： 混淆了dijkstra和一般最短路算法的思想，導(dǎo)致遲遲得不到想要的結(jié)果。最后參考了層序遍歷的思想，改掉了這個bug。第三天： 題目說Ne不超過10⁵，但是開邊的時候數(shù)組要開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();        // 上一波出隊, 更新狀態(tài)        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;}

關(guān)鍵詞：