Dijkstra: Shortest Reach 2

• Time : O(eloge)
• Space : O(v + e)

vector<int> shortestReach(int n, vector<vector<int>> edges, int s) {
    vector<vector<pair<int, int>>> adj(n + 1);
    vector<int> dis(n + 1, INT_MAX);
    for(auto& e : edges) {
        int u = e[0], v = e[1], w = e[2];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    dis[s] = 0;
    while(!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if(dis[u] != w) continue;
        for(auto& [v, weight] : adj[u]) {
            if(dis[v] > weight + w) {
                dis[v] = weight + w;
                pq.push({dis[v], v});
            }
        }
    }

    vector<int> res;
    for(int i = 1; i <= n; i++) {
        if(i == s) continue;
        if(dis[i] == INT_MAX) res.push_back(-1);
        else res.push_back(dis[i]);
    }
    return res;
}