問(wèn)題 C: Cities

時(shí)間限制:?1 Sec??內(nèi)存限制:?128 MB
提交:?87??解決:?61
[提交][狀態(tài)][討論版][命題人: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;} }

貪心題

轉(zhuǎn)載于:https://www.cnblogs.com/hao-tian/p/9080582.html

總結(jié)

以上是生活随笔為你收集整理的Cities的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。