Codeforces Round #303 (Div. 2) E. Paths and Trees

問題

Problem - 545E - Codeforces

解法

ダイクストラで最短距離求めた後root以外の各頂点uについてd[u]-e.cost == d[e.to]となるやつのうちe.costが最小のやつを選ぶ。

以下ソースコード

struct edge {
    int to;
    ll cost;
    int id;
    edge(int t, ll c, int i) : to(t), cost(c), id(i) {}
    edge() {}
};

const int MAXN = 300030;
const ll INF = 1ll<<55;
vector<edge> G[MAXN];
int parent[MAXN];
ll d[MAXN];

void dijkstra(int s, int n) {
    priority_queue<pair<ll, int> > que;
    for (int i = 0; i < n; i++) {
        d[i] = INF;
    }
    d[s] = 0;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto now = que.top(); que.pop();
        ll dist = -now.first;
        int v = now.second;
        if (d[v] < dist) continue;
        for (auto e : G[v]) {
            if (d[e.to] > d[v]+e.cost) {
                d[e.to] = d[v]+e.cost;
                que.push(make_pair(-d[e.to], e.to));
            }
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        ll cost;
        cin >> u >> v >> cost;
        u--; v--;
        G[u].push_back(edge(v, cost, i+1));
        G[v].push_back(edge(u, cost, i+1));
    }
    int s;
    cin >> s;
    s--;
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
    dijkstra(s, n);
    vector<int> ans;
    ll all = 0;
    for (int i = 0; i < n; i++) {
        if (i == s) continue;
        ll minCost = INF;
        int id = 0;
        for (auto e : G[i]) {
            if (d[i]-e.cost == d[e.to]) {
                if (minCost > e.cost) {
                    minCost = e.cost;
                    id = e.id;
                }
            }
        }
        all += minCost;
        ans.push_back(id);
    }
    cout << all << endl;
    sort(ans.begin(), ans.end());
    for (int el : ans) {
        cout << el << " ";
    }
    cout << endl;
    return 0;
}