lessons/参考实现/05-最短路与类最短路/CodeForces-545E.cpp

#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
struct Edge { int to, id; long long weight; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<vector<Edge>> g(n);
    for (int id = 0; id < m; ++id) {
        int u, v; long long w; cin >> u >> v >> w; --u; --v;
        g[u].push_back({v, id, w}); g[v].push_back({u, id, w});
    }
    int source; cin >> source; --source;
    const long long inf = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n, inf), parent_weight(n, inf);
    vector<int> parent_edge(n, -1);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    dist[source] = 0; pq.push({0, source});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (Edge e : g[u]) {
            long long candidate = d + e.weight;
            if (candidate < dist[e.to]) {
                dist[e.to] = candidate;
                parent_weight[e.to] = e.weight;
                parent_edge[e.to] = e.id;
                pq.push({candidate, e.to});
            } else if (candidate == dist[e.to] && e.weight < parent_weight[e.to]) {
                parent_weight[e.to] = e.weight;
                parent_edge[e.to] = e.id;
            }
        }
    }
    long long total = 0;
    for (int v = 0; v < n; ++v) if (v != source) total += parent_weight[v];
    cout << total << '\n';
    for (int v = 0; v < n; ++v) if (v != source) cout << parent_edge[v] + 1 << ' ';
    cout << '\n';
}