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

Submission #242716

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>
#include <climits>

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 MP make_pair
#define PB push_back
#define F first
#define S second
#define INF (LLONG_MAX/2)
#define EPS 1e-10

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

struct Edge{
int to, cost;
};

int N, M;
int c,a,b,r;
vector<vector<Edge> >G(100005);
ll mincost[10005];
bool used[100005];

ll prim(){
rep(i, N){
mincost[i] = INF;
used[i] = false;
}

mincost[0] = 0;
ll ret = 0;
int usedNum =0 ;
priority_queue<pi, vector<pi>, greater<pi> >q;
q.push(MP(0, 0));

while(!q.empty()){
pi p = q.top(); q.pop();
int v = p.S;
if(used[v]) continue;
ret += p.first;
if(++usedNum == N) return ret;

for(unsigned i = 0; i < G[v].size(); ++i){
Edge e = G[v][i];
if(!used[e.to] && e.cost < mincost[e.to]){
mincost[e.to] = e.cost;
q.push(MP(e.cost, e.to));
}
}
}
return -1;

}

int main(){
scanf("%d%d", &N, &M);

rep(i, N){
scanf("%d", &c);
Edge e; e.to = N; e.cost = c;
G[i].PB(e); e.to = i;
G[N].PB(e);
}
rep(i, M){
scanf("%d%d%d", &a, &b, &r); a--; b--;
Edge e; e.to = a; e.cost = r;
G[b].PB(e); e.to = b;
G[a].PB(e);
}
N++;
printf("%lld\n", prim());
return 0;
}
```

#### Submission Info

Submission Time 2014-09-28 02:20:53+0900 C - 高橋君と国家 raven38 C++ (G++ 4.6.4) 0 1874 Byte WA 467 ms 11548 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:78:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:81:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:87: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