弱化版用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 coder2009 @ 2023-08-27 13:34:45

rt，求助原因，请各位神犇指教

by qczrz6v4nhp6u @ 2023-08-27 13:40:39

const int INF = 1e10;

爆 int 了

by qczrz6v4nhp6u @ 2023-08-27 13:41:11

@coder2009

by problemThief @ 2023-08-27 13:45:33

@coder2009

by coder2009 @ 2023-08-27 13:57:49

@ScatteredHope 改到2e9或者1e9也都WA了………………

by Eznibuil @ 2023-08-27 14:01:43

@ScatteredHope 冷知识：强转时会直接转成 int 最大值，所以并没有爆。

by Nityacke @ 2023-08-27 14:06:51

@coder2009 dist 用 longlong ，INF 调大

by coder2009 @ 2023-08-27 14:10:55

#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<int, long long>, vector<pair<int, long long>>, greater<pair<int, long long>>> 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] << " ";
        }
    }
};

@Ethereal_shadow 不瞒你说我试过了，但最后一个点就是死过不去

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

@Eznibuil 啊，是吗

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

@coder2009 有没有一种可能，优先队列那部分 int 和 long long 开反了