該比賽已結束，您無法在比賽模式下遞交該題目。您可以點選“在題庫中開啟”以普通模式檢視和遞交本題。

Problem Description

Author: louishuang

有人剛學完dijkstra後信誓旦旦地寫出來了

結果只要輸入的$N > 2$就會死掉

幫他找找蟲吧

修改 $\le 2$ 個字元且 AC： 100 分。

修改 $\le 20$ 個字元且 AC： 50 分。

否則：0 分。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    long long weight;
    bool operator>(const Edge& other) const {
        return weight > other.weight;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, start;
    if (!(cin >> n >> m >> start)) return 0;
   
    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<long long> dist{n + 1, INF};
    vector<bool> visited(n + 1, false);
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;

    dist[start] = 0;
    pq.push({start, 0});

    while (!pq.empty()) {
        int u = pq.top().to;
        pq.pop();
       
        if (visited[u]) continue;
        visited[u] = true;

        for (auto& edge : adj[u]) {
            int v = edge.to;
            long long w = edge.weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({v, dist[v]});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << "-1 ";
        else cout << dist[i] << " ";
    }
    cout << "\n";
    return 0;
}

3 3 1
1 2 2
2 3 3
1 3 6

0 2 5