题目
F. Freeway-travelling Salesman
代码
Code
// 最小生成树 Prim
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 1e5 + 10;
struct Edge
{
int v;
LL w;
};
vector<Edge> adj[N]; // adj[u] 表示从节点 u 出发的 邻接边u->v 的列表, 边指向v, 边权为w
LL dis[N]; // 用于prim最小生成树
bool vis[N]; // 标记最小生成树过程中节点i是否已经纳入生成树
void solv()
{
int n, m;
cin >> n >> m;
int u, v, w;
for (int i = 1; i <= m; i ++)
{
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
// Prim
priority_queue<PII, vector<PII>, greater<PII>> q; // 堆优化 Prim, 元素为 {d, u}, d为节点u距离当前生成树已有点集合(vis表示为true的节点)的最小距离
memset(dis, 0x3f, sizeof dis); dis[1] = 0;
q.push({0, 1});
vector<int> ans;
LL tot = 0; // 最小生成树边权和
while (q.size())
{
int u = q.top().second; q.pop();
if (vis[u]) continue;
// 将节点u放入生成树节点集合
vis[u] = true;
ans.push_back(u); // 记录节点拓展顺序
tot += dis[u];
for (auto [v, w]: adj[u]) // cpp语法, 遍历adj[u]中的所有元素, 每个pair的值为{v, w}
{
if (w < dis[v]) // 注意prim与dijkstra的堆优化写法很像, 这句是最大的差别; 更新距离是节点v到生成树节点集合, 而不是起点
{
dis[v] = w;
q.push({dis[v], v});
}
}
}
cout << tot << ' ' << n << endl;
for (auto u: ans) cout << u << ' ';
cout << endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while (T --)
{
solv();
}
return 0;
}