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

Submission #315233

Source Code Expand

Copy
```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef queue<int> qi;

struct Edge{
int u,v; ll cost;
bool operator<(const Edge &a)const{
return cost < a.cost;
}
};

struct UnionFind{
int par[100005];
int rank[100005];
UnionFind(){ init(); }
void init(){
rep(i,100005){
par[i] = i;
rank[0];
}
}
int find(int x){
if(x==par[x]) return x;
return par[x] = find(par[x]);
}
int same(int x, int y){
return find(x)==find(y);
}
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]++;
}
}
};

int N,M;
vector<Edge>es;

int main(){
scanf("%d%d",&N,&M);
rep(i,N){
ll c;
scanf("%lld", &c);
es.PB((Edge){0,i+1,c});
}
rep(i,M){
int a, b; ll r;
scanf("%d%d%lld", &a,&b,&r);
es.PB((Edge){a,b,r});
}

sort(es.begin(), es.end());

UnionFind uf;
ll res = 0;
rep(i,es.size()){
Edge e = es[i];
if(!uf.same(e.u, e.v)){
uf.unite(e.u, e.v);
res += e.cost;
}
}

printf("%lld\n", res);
return 0;
}
```

#### Submission Info

Submission Time 2015-01-06 15:43:46+0900 C - 高橋君と国家 raven38 C++ (G++ 4.6.4) 100 1975 Byte AC 249 ms 9124 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:77:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:80:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:85:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
```

#### Test Cases

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