弱化版用dijkstra过了，同款代码但标准版#6WA了

coder2009 @ 2023-08-27 13:33:37

#include <bits/stdc++.h>
using namespace std;

#define endl '\n';
struct shortest_path {
    struct edge {
        int to;
        int l;
    };
    const int INF = 1e10;
    vector<int> dist;
    vector<bool> b;
    vector<vector<edge>> g;
    shortest_path(int n) :
                           dist(n + 1, INF), g(n), b(n, false) {}

    void dijkstra (int n, int m, int s) { 
        for (int i = 0; i < m; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            --u;
            --v;
            g[u].push_back({v, w});
        }
        dist[s] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> ds;
        ds.emplace(0, s);
        while (!ds.empty()) {
            auto k = ds.top().second;
            ds.pop();
            if (b[k]) {
                continue;
            }
            for (auto i : g[k]) {
                if (dist[k] + i.l < dist[i.to] && dist[k] + i.l > 0) {
                    dist[i.to] = dist[k] + i.l;
                    ds.emplace(dist[i.to], i.to);
                }
            }
            b[k] = true;
        }
        for (int i = 0; i < n; ++i) {
            cout << dist[i] << " ";
        }
    }
};

void best_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, s;
    cin >> n >> m >> s;
    shortest_path sp(n);
    sp.dijkstra(n, m, s - 1);
}

int main() {
    best_coder();

    // 返回
    return 0;
}

by qczrz6v4nhp6u @ 2023-08-27 14:21:55

@coder2009 另外，编译时添加 -Wall 指令可以方便地发现代码中类似于这种的错误。

by coder2009 @ 2023-08-27 14:24:43

@ScatteredHope 还真是，我改了试试

by coder2009 @ 2023-08-27 14:26:38

@ScatteredHope 虽然但是我还是Wa了………………就离谱啊

by qczrz6v4nhp6u @ 2023-08-27 14:26:46

@ScatteredHope 6，-Wall 显示不出这种错误。当我没说。

by qczrz6v4nhp6u @ 2023-08-27 14:27:04

@coder2009 啊，我测了一遍过了啊

by qczrz6v4nhp6u @ 2023-08-27 14:27:20

https://www.luogu.com.cn/record/122969019

by coder2009 @ 2023-08-27 14:37:57

@ScatteredHope https://www.luogu.com.cn/record/122969283 我确实是WA了

by qczrz6v4nhp6u @ 2023-08-27 14:41:06

@coder2009 我看不到你的代码 麻烦发一下

by coder2009 @ 2023-08-27 14:41:56

@ScatteredHope 神犇求代码，说真的我心态要炸了

by coder2009 @ 2023-08-27 14:45:54

#include <bits/stdc++.h>
using namespace std;

#define endl '\n';
struct shortest_path {
    struct edge {
        int to;
        long long l;
    };
    const long long INF = 1e17;
    vector<long long> dist;
    vector<bool> b;
    vector<vector<edge>> g;
    shortest_path(int n) :
            dist(n + 1, INF), g(n), b(n, false) {}

    void dijkstra (int n, int m, int s) {
        for (int i = 0; i < m; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            --u;
            --v;
            g[u].push_back({v, w});
        }
        dist[s] = 0;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> ds;
        for (int i = 0; i < n; ++i) {
            ds.emplace(dist[i], i);
        }
        while (!ds.empty()) {
            auto k = ds.top().second;
            ds.pop();
            if (b[k]) {
                continue;
            }
            for (auto i : g[k]) {
                if (dist[k] + i.l < dist[i.to] && dist[k] + i.l > 0) {
                    dist[i.to] = dist[k] + i.l;
                    ds.emplace(dist[i.to], i.to);
                }
            }
            b[k] = true;
        }
        for (int i = 0; i < n; ++i) {
            cout << dist[i] << " ";
        }
    }
};

void best_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, s;
    cin >> n >> m >> s;
    shortest_path sp(n);
    sp.dijkstra(n, m, s - 1);
}

int main() {
    best_coder();

    // 返回
    return 0;
}

@ScatteredHope