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

Submission #241799

Source Code Expand

Copy
```#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<25;
typedef pair<int,int> P;
typedef long long ll;
typedef unsigned long long ull;
struct edge {
int src, dst, len;
edge(int s, int d, int l)
: src(s), dst(d), len(l) { }
};
typedef vector<edge> vertex;
typedef vector<vertex> graph;
bool operator < (const edge& e, const edge& f)
{
return e.len > f.len;
}
#define MAX_N 100010
struct UF {
int par[MAX_N],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] = par[x];
if(rank[x] == rank[y]) rank[y]++;
}
}

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

int main(){
int N, M;
cin>>N>>M;
N++;
graph g(N);
for(int i = 1; i < N; i++){
int c;
cin>>c;
g[0].push_back(edge(0, i, c));
g[i].push_back(edge(i, 0, c));
}
for(int i = 0; i < M; i++){
int a, b, r;
cin>>a>>b>>r;
g[a].push_back(edge(a, b, r));
g[b].push_back(edge(b, a ,r));
}

UF uf;
uf.init(N);
priority_queue<edge> q;
for(int i = 0; i < N; i++){
for(int j = 0; j < g[i].size(); j++){
edge e = g[i][j];
if(i < e.dst) q.push(e);
}
}

ll res = 0;
while(!q.empty()){
edge e = q.top(); q.pop();
if(!uf.same(e.src, e.dst)){
uf.unite(e.src, e.dst);
res += e.len;
}
}
cout<<res<<endl;
return 0;
}
```

#### Submission Info

Submission Time 2014-09-27 21:50:05+0900 C - 高橋君と国家 Lepton C++ (G++ 4.6.4) 100 2039 Byte AC 705 ms 21140 KB

#### Judge Result

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