Cities_李大同

Cities

发布时间：2020-12-14 04:49:54 所属栏目：大数据来源：网络整理

导读：问题 C: Cities 时间限制:?1 Sec?? 内存限制:?128 MB 提交:?87?? 解决:?61 [提交][状态][讨论版][命题人: admin] 题目描述 There are n cities in Byteland,and the ith?city has a value ai. The cost of building a bidirectional road between two cities

问题 C: Cities

时间限制:?1 Sec??内存限制:?128 MB
提交:?87??解决:?61
[提交][状态][讨论版][命题人:admin]

题目描述

There are n cities in Byteland,and the ith?city has a value ai. The cost of building a bidirectional road between two cities is the sum of their values. Please calculate the minimum cost of connecting these cities,which means any two cities can reach each other.

输入

The first line is an integer T(T≤10^5),representing the number of test cases.
For each test case,the first line is an integer n(n≤10^5),representing the number of cities,the second line are n positive integers ai(ai≤10^5),representing their values.

输出

For each test case,output an integer ans,the minimum cost of connecting these cities.

样例输入

样例输出

12
0

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        if(n==1)
        {
            cout<<0<<endl;
            continue;
        }
        int a[100005];
        cin>>a[0];
        int minx = a[0];
        int index = 0;
        for(int i=1;i<n;i++)
        {
            cin>>a[i];
            if(a[i]<minx)
            {
                minx = a[i];
                index = i;
            }
        }
        long long int ans = 0;
        for(int i=0;i<n;i++)
        {
            if(i!=index)
            {
                ans+=minx+a[i];
            }
        }
        cout<<ans<<endl;
    }
}

贪心题

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!