[CF545E] Paths and Trees - 最短路
Description
给定一张带正权的无向图和一个源点,求边权和最小的最短路径树。
Solution
跑最短路的时候,转移时尽量让当前边的边权最小
记录一下前驱,最后连出来就是答案
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
struct Edge
{
int u, v, w, id;
};
struct Node
{
int d;
int p;
bool operator<(const Node &rhs) const
{
return d > rhs.d;
}
};
int n, m;
vector<int> g[N]; // 存的是边的 id
vector<Edge> edges;
int vis[N], dis[N], pre[N];
signed main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back(edges.size());
edges.push_back({u, v, w, i});
g[v].push_back(edges.size());
edges.push_back({v, u, w, i});
}
int s;
cin >> s;
priority_queue<Node> que;
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
que.push({0, s});
while (que.size())
{
auto [d, p] = que.top();
que.pop();
if (vis[p])
continue;
vis[p] = 1;
for (auto i : g[p])
{
auto [_, q, w, id] = edges[i];
if (dis[q] > dis[p] + w)
{
dis[q] = dis[p] + w;
pre[q] = i;
que.push({dis[q], q});
}
else if (dis[q] == dis[p] + w && w < edges[pre[q]].w)
{
pre[q] = i;
}
}
}
vector<int> ans;
int ansval = 0;
for (int i = 1; i <= n; i++)
{
if (i == s)
continue;
ans.push_back(edges[pre[i]].id);
ansval += edges[pre[i]].w;
}
sort(ans.begin(), ans.end());
cout << ansval << endl;
for (auto i : ans)
cout << i << " ";
}