算法训练 安慰奶牛

  • 时间:
  • 来源:互联网

如果可以,可以陪你千年不老,千年只想眷顾你倾城一笑;如果愿意,愿意陪你永世不离,永世只愿留恋你青丝白衣。

这个测试数据的答案是错误的!!! 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
//#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int inf = 1<<30;
int n,p,sum,mi=inf;
int s[100010],x[100010];
struct node
{
    int st;
    int ed;
    int w;
} G[100010];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int fd(int z)
{
    if(x[z]==z)
        return z;
    int ls=fd(x[z]);
    x[z]=ls;
    return ls;
}
int main()
{
    cin>>n>>p;
    for(int i=1; i<=n; i++)
    {
        cin>>s[i];
        x[i]=i;
        mi=min(mi,s[i]);
    }
    for(int i=1; i<=p; i++)
    {
        cin>>G[i].st>>G[i].ed>>G[i].w;
        G[i].w=2*G[i].w+s[G[i].st]+s[G[i].ed];
    }
    sort(G+1,G+p+1,cmp);
    for(int i=1; i<=p; i++)
    {
        int u=fd(G[i].st);
        int v=fd(G[i].ed);
        if(u!=v)
        {
            sum+=G[i].w;
            x[u]=v;
        }
    }
    cout<<sum+mi<<endl;
    return 0;
}

 

0k-ok
发布了778 篇原创文章 · 获赞 39 · 访问量 3万+

本文链接http://element-ui.cn/news/show-1547.aspx