首页 > 其他 > 详细

Cities

时间:2018-05-24 00:53:17      阅读:63      评论:0      收藏:0      [点我收藏+]

标签:direct   stat   mini   positive   XA   cti   minimum   inf   pac   

问题 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.

样例输入

2
4
1 2 3 4
1
1

样例输出

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;
    }
}

贪心题

Cities

标签:direct   stat   mini   positive   XA   cti   minimum   inf   pac   

原文:https://www.cnblogs.com/hao-tian/p/9080582.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号