- 联络员(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%
 - 上传者