Codeforces 545E(最短路修改松弛+贪心)

Codeforces 545E
题意：给定一个无向图和一个点$u$，找出若干条边组成一个子树，要求这个子树中$u$到其他个点的最短距离与在原图中的相等，并且要求子树所有边的权重之和最小，求出最小值并输出子树的边号。
修改版dij。在最短路的时候，每个点存它被松弛的那条边，这条边尽量在保证最短路的情况下最小。因为这样就能使边能够更加合理利用，贪心思想。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const LL MAXN = 300000 + 5, INF = 4411686018427387900;

struct edge {
    LL v, wi;
}ed[MAXN * 2];
struct node {
    LL u, d;
    bool operator < (const node &b) const {
        return d > b.d;
    }
};

LL n, m, en, st, dis[MAXN], vis[MAXN];
std::pair<LL, LL > bst[MAXN];
std::vector<LL > G[MAXN];
std::priority_queue<node > q;

inline void ins(LL u, LL v, LL w) {
    ed[++en] = (edge){v, w}, G[u].push_back(en);
    ed[++en] = (edge){u, w}, G[v].push_back(en);
}

void dij(LL s) {
    for (LL i = 0; i <= n; i++) vis[i] = 0, dis[i] = bst[i].first = INF;
    dis[s] = 0, q.push((node){s, 0});
    while (!q.empty()) {
        node p = q.top(); q.pop();
        if (vis[p.u]) continue; vis[p.u] = 1;
        for (LL i = 0; i < (LL)G[p.u].size(); i++) {
            edge &e = ed[G[p.u][i]];
            if (dis[e.v] > dis[p.u] + e.wi) 
                dis[e.v] = dis[p.u] + e.wi, bst[e.v].first = e.wi, bst[e.v].second = G[p.u][i], q.push((node){e.v, dis[e.v]});
            else if (dis[e.v] == dis[p.u] + e.wi && e.wi < bst[e.v].first) bst[e.v].first = e.wi, bst[e.v].second = G[p.u][i];
        }
    }
}

void clean() {
    en = 0;
}
int solve() {
    clean();
    for (LL u, v, w, i = 1; i <= m; i++) scanf("%lld%lld%lld", &u, &v, &w), ins(u, v, w);
    scanf("%lld", &st);
    dij(st);
    LL ans1 = 0;
    for (LL i = 1; i <= n; i++) if (i != st) ans1 += bst[i].first;
    printf("%lld\n", ans1);
    for (LL i = 1; i <= n; i++) if (i != st) printf("%lld ", (bst[i].second + 1) / 2);
    return 0; 
}
int main() {
    scanf("%lld%lld", &n, &m), solve();
    return 0;
}