Paths and Trees 题解
最短路径树：一个图抽出一个树，使得根节点到每个点的距离就是图中根节点到点的最短路。
很容易想到先求出最短路图，这样就能得到根节点到每个点的最短路所经过的边。
然后再考虑怎么在最短路图上求出一个边权和最小的树。
发现在有向图上求一个边权和最小的树不就是求最小树形图吗，直接朱刘算法即可。
因为最短路图是 DAG，所以直接朱刘只会跑一遍。
#include <bits/stdc++.h>
#define int long long
#define __int32 int
#define __int64 long long
#define db long double
#define eps 1e-12
const int N = 6e5 + 10, M = 2e5 + 10, inf = 1e9 + 10;
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; ! isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x *= f;
}
using namespace std;
struct Ed {
int v, w, id;
} ;
struct edge {
int u, v, w, id;
} E[N];
bool cmp( edge a, edge b) { return a.w < b.w; }
vector< Ed> G[N];
struct node {
int w, v;
bool operator < ( const node & rhs) const { return w > rhs.w; }
} ;
priority_queue< node> q;
int dis[N], vis[N], cost[N], pre[N];
void dij( int s) {
memset(dis, 127, sizeof(dis)), memset(vis, 0, sizeof(vis));
q.push({0, s}), dis[s] = 0;
while (q.size()) {
int u = q.top().v; q.pop();
if (vis[u]) continue; ; vis[u] = 1;
for ( auto i : G[u]) {
int v = i.v;
if (dis[v] > dis[u] + i.w) dis[v] = dis[u] + i.w, q.push({dis[v], v});
}
}
}
int n, m, s, tot, ans;
signed main() {
n = read(), m = read();
for ( int i = 1, u, v, w; i <= m; i ++) u = read(), v = read(), w = read(),
G[u].push_back({v, w, i}), G[v].push_back({u, w, i});
s = read();
dij(s);
for ( int u = 1; u <= n; u ++) for ( auto i : G[u]) if (dis[u] + i.w == dis[i.v]) E[++ tot] = {u, i.v, i.w, i.id};
sort(E + 1, E + tot + 1, cmp);
memset(cost, 127, sizeof cost);
for ( int i = 1; i <= tot; i ++) {
int u = E[i].u, v = E[i].v;
if (cost[v] > E[i].w) cost[v] = E[i].w, pre[v] = E[i].id;
}
cost[s] = 0;
for ( int i = 1; i <= n; i ++) ans += cost[i];
cout << ans << endl;
for ( int i = 1; i <= n; i ++) if (pre[i]) printf("%lld ", pre[i]);
}