Contest Duration: ~ (local time) (90 minutes) Back to Home

Submission #242891

Source Code Expand

Copy
```#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>

#pragma warning( disable: 4996 )

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

#define INF 1000000000
#define EPS 1e-10

#define MAX_N 100002
#define MAX_M 300002

int N, M;
int c[MAX_N];
int a[MAX_M];
int b[MAX_M];
int r[MAX_M];

int E = 0;

struct edge{
int from;
int to;
int cost;
};

edge es[MAX_M];

//親都市をNにする
int par[MAX_N];
int Rank[MAX_N];

void init(int n){
for (int i = 0; i <= n; i++){
par[i] = i;
Rank[i] = 0;
}
}

int find(int x){
if (par[x] == x)
return x;
else
return par[x] = find(par[x]);
}

void unite(int x, int y){

x = find(x);
y = find(y);
if (x == y)
return;

if (Rank[x] < Rank[y]){
par[x] = y;
}
else{
par[y] = x;
if (Rank[x] == Rank[y])
Rank[x]++;
}

}

bool same(int x, int y){
return find(x) == find(y);
}

bool comp(const edge& e1, const edge& e2){
return e1.cost < e2.cost;
}

int solve(){
int ans = 0;

sort(es, es + E, comp);

init(N);

for (int i = 0; i < E; i++){
edge e = es[i];
if (!same(e.from, e.to)){
unite(e.from, e.to);
ans += e.cost;
}
}

return ans;
}

int main() {

cin >> N >> M;
for (int i = 0; i < N; i++){
cin >> c[i];
es[E] = {N, i, c[i]};
E++;
}

for (int i = 0; i < M; i++){
cin >> a[i] >> b[i] >> r[i];
a[i]--;
b[i]--;
es[E] = { a[i], b[i], r[i] };
E++;
}

cout << solve() << endl;

return 0;
}```

#### Submission Info

Submission Time 2014-09-28 13:55:49+0900 C - 高橋君と国家 taketake0609 C++ (G++ 4.6.4) 0 1919 Byte WA 564 ms 7900 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:122:22: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x [enabled by default]
./Main.cpp:122:22: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x [enabled by default]
./Main.cpp:130:30: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x [enabled by default]
./Main.cpp:130:30: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x [enabled by default]
```

#### Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory