#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
typedef pair<int, int> p;
vector<p>vec[maxn];
int vis[maxn];
int main() {
int n, m;
int u, v, val;
int ans = 0;
scanf("%d%d", &n, &m);
memset(vis, 0, sizeof(vis));
for (int i = 1;i <= m;++i) {
scanf("%d%d%d", &u, &v, &val);//读入边
vec[u].push_back(p(val, v));//顶点u到v距离为val
vec[v].push_back(p(val, u));//顶点v到u距离为val
}
priority_queue<p, vector<p>, greater<p> >pq;//优先队列
vis[1] = 1;
for (int i = 0;i < vec[1].size();++i) {
pq.push(vec[1][i]);//将与1相连的顶点入队
}
while (!pq.empty()) {
p now = pq.top();
pq.pop();
if (!vis[now.second]) {//当前顶点没有被访问过
vis[now.second] = 1;//标记已经被访问过
ans += now.first;
}
for (int i = 0;i < vec[now.second].size();++i) {//枚举与刚刚进树的这个顶点
if (!vis[vec[now.second][i].second]) {//相邻的顶点
pq.push(vec[now.second][i]);//将其进队列 优先队列会自动排序
}
}
}
printf("%d\n", ans);
return 0;
}
原文链接: https://www.cnblogs.com/zzqwtc/p/14127378.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/372980
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!