- 联络员(liaison)
- 2020-07-15 14:14:06 @
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
vector <pair <int,int> > g[5123];
bool vis[5123];
int n,m,wei[5001];
int prim()
{
int ans=0;
for(int i=2;i<=n;i++) wei[i]=INF;
for(int i=1;i<=n;i++)
{
int cur=1;
while(vis[cur]) cur++;
for(int nxt=cur+1;nxt<=n;nxt++) if(!vis[nxt]&&wei[nxt]<wei[cur]) cur=nxt;
vis[cur]=1;
ans+=wei[cur];
for(int j=0;j<g[cur].size();j++)
{
int tmp=g[cur][j].first;
if(!vis[tmp])
{
int w=g[cur][j].second;
if(w<wei[tmp]) wei[tmp]=w;
}
}
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int n1,n2,w;
cin>>n1>>n2>>w;
g[n1].push_back(make_pair(n2,w));
g[n2].push_back(make_pair(n1,w));
}
int ans=prim();
if(ans>=INF) cout<<"orz";
else cout<<ans;
return 0;
}
2 条评论
-
最牛刷题者 LV 3 @ 2020-07-15 14:24:38
@admin
-
2020-07-15 14:14:35@
评测信息:
FileNotFoundError('output/liaison10.out',)
- 1
信息
- 难度
- 10
- 分类
- (无)
- 标签
- 递交数
- 41
- 已通过
- 0
- 通过率
- 0%
- 上传者