Submission #242718


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[100005];
bool used[100005];

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

  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;
    used[v] = true;
    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
Task C - 高橋君と国家
User raven38
Language C++ (G++ 4.6.4)
Score 100
Code Size 1877 Byte
Status
Exec Time 409 ms
Memory 13960 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
Sample 0 / 0 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt
Subtask1 10 / 10 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt
Subtask2 20 / 20 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt
Subtask3 30 / 30 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt
Subtask4 40 / 40 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt, subtask4-01.txt, subtask4-02.txt, subtask4-03.txt, subtask4-04.txt, subtask4-05.txt, subtask4-06.txt, subtask4-07.txt, subtask4-08.txt, subtask4-09.txt, subtask4-10.txt, subtask4-11.txt, subtask4-12.txt, subtask4-13.txt, subtask4-14.txt, subtask4-15.txt, subtask4-16.txt, subtask4-17.txt, subtask4-18.txt, subtask4-19.txt, subtask4-20.txt, subtask4-21.txt, subtask4-22.txt, subtask4-23.txt, subtask4-24.txt, subtask4-25.txt, subtask4-26.txt, subtask4-27.txt, subtask4-28.txt, subtask4-29.txt, subtask4-30.txt
Case Name Status Exec Time Memory
subtask0-sample-01.txt 32 ms 3040 KB
subtask0-sample-02.txt 30 ms 3104 KB
subtask0-sample-03.txt 31 ms 3236 KB
subtask1-01.txt 28 ms 3228 KB
subtask1-02.txt 29 ms 3108 KB
subtask1-03.txt 29 ms 3092 KB
subtask1-04.txt 30 ms 3100 KB
subtask1-05.txt 30 ms 3232 KB
subtask1-06.txt 27 ms 3100 KB
subtask1-07.txt 27 ms 3100 KB
subtask1-08.txt 31 ms 3052 KB
subtask1-09.txt 30 ms 3100 KB
subtask1-10.txt 29 ms 3232 KB
subtask1-11.txt 30 ms 3232 KB
subtask1-12.txt 31 ms 3112 KB
subtask1-13.txt 30 ms 3232 KB
subtask1-14.txt 28 ms 3040 KB
subtask1-15.txt 28 ms 3104 KB
subtask1-16.txt 27 ms 3112 KB
subtask1-17.txt 31 ms 3032 KB
subtask1-18.txt 32 ms 3096 KB
subtask1-19.txt 28 ms 3220 KB
subtask1-20.txt 30 ms 3096 KB
subtask1-21.txt 31 ms 3036 KB
subtask1-22.txt 29 ms 3116 KB
subtask1-23.txt 30 ms 3104 KB
subtask1-24.txt 29 ms 3112 KB
subtask1-25.txt 31 ms 3228 KB
subtask1-26.txt 29 ms 3100 KB
subtask1-27.txt 30 ms 3036 KB
subtask1-28.txt 29 ms 3096 KB
subtask1-29.txt 28 ms 3232 KB
subtask1-30.txt 28 ms 3232 KB
subtask2-01.txt 27 ms 3216 KB
subtask2-02.txt 29 ms 3228 KB
subtask2-03.txt 27 ms 3228 KB
subtask2-04.txt 30 ms 3108 KB
subtask2-05.txt 29 ms 3040 KB
subtask2-06.txt 27 ms 3112 KB
subtask2-07.txt 29 ms 3104 KB
subtask2-08.txt 29 ms 3228 KB
subtask2-09.txt 29 ms 3228 KB
subtask2-10.txt 28 ms 3108 KB
subtask2-11.txt 28 ms 3236 KB
subtask2-12.txt 30 ms 3236 KB
subtask2-13.txt 28 ms 3100 KB
subtask2-14.txt 29 ms 3044 KB
subtask2-15.txt 28 ms 3112 KB
subtask2-16.txt 29 ms 3108 KB
subtask2-17.txt 29 ms 3112 KB
subtask2-18.txt 29 ms 3040 KB
subtask2-19.txt 30 ms 3228 KB
subtask2-20.txt 28 ms 3108 KB
subtask2-21.txt 28 ms 3224 KB
subtask2-22.txt 29 ms 3104 KB
subtask2-23.txt 28 ms 3232 KB
subtask2-24.txt 29 ms 3040 KB
subtask2-25.txt 29 ms 3224 KB
subtask2-26.txt 32 ms 3048 KB
subtask2-27.txt 32 ms 3112 KB
subtask2-28.txt 29 ms 3096 KB
subtask2-29.txt 29 ms 3076 KB
subtask2-30.txt 32 ms 3064 KB
subtask3-01.txt 30 ms 3104 KB
subtask3-02.txt 31 ms 3116 KB
subtask3-03.txt 29 ms 3168 KB
subtask3-04.txt 33 ms 3168 KB
subtask3-05.txt 31 ms 3248 KB
subtask3-06.txt 30 ms 3236 KB
subtask3-07.txt 32 ms 3228 KB
subtask3-08.txt 32 ms 3360 KB
subtask3-09.txt 34 ms 3364 KB
subtask3-10.txt 33 ms 3368 KB
subtask3-11.txt 32 ms 3368 KB
subtask3-12.txt 32 ms 3364 KB
subtask3-13.txt 32 ms 3372 KB
subtask3-14.txt 35 ms 3488 KB
subtask3-15.txt 37 ms 3432 KB
subtask3-16.txt 36 ms 3492 KB
subtask3-17.txt 35 ms 3496 KB
subtask3-18.txt 34 ms 3492 KB
subtask3-19.txt 37 ms 3484 KB
subtask3-20.txt 34 ms 3488 KB
subtask3-21.txt 34 ms 3496 KB
subtask3-22.txt 34 ms 3616 KB
subtask3-23.txt 36 ms 3492 KB
subtask3-24.txt 35 ms 3488 KB
subtask3-25.txt 36 ms 3476 KB
subtask3-26.txt 34 ms 3484 KB
subtask3-27.txt 34 ms 3492 KB
subtask3-28.txt 34 ms 3492 KB
subtask3-29.txt 36 ms 3492 KB
subtask3-30.txt 37 ms 3492 KB
subtask4-01.txt 39 ms 3624 KB
subtask4-02.txt 45 ms 4000 KB
subtask4-03.txt 51 ms 4500 KB
subtask4-04.txt 143 ms 7832 KB
subtask4-05.txt 188 ms 10520 KB
subtask4-06.txt 302 ms 12696 KB
subtask4-07.txt 305 ms 12756 KB
subtask4-08.txt 210 ms 11156 KB
subtask4-09.txt 265 ms 12060 KB
subtask4-10.txt 366 ms 13848 KB
subtask4-11.txt 363 ms 13860 KB
subtask4-12.txt 383 ms 13844 KB
subtask4-13.txt 361 ms 13776 KB
subtask4-14.txt 386 ms 13852 KB
subtask4-15.txt 407 ms 13856 KB
subtask4-16.txt 409 ms 13844 KB
subtask4-17.txt 336 ms 13848 KB
subtask4-18.txt 354 ms 13960 KB
subtask4-19.txt 379 ms 13840 KB
subtask4-20.txt 378 ms 13844 KB
subtask4-21.txt 351 ms 13836 KB
subtask4-22.txt 359 ms 13836 KB
subtask4-23.txt 332 ms 13844 KB
subtask4-24.txt 351 ms 13856 KB
subtask4-25.txt 335 ms 13772 KB
subtask4-26.txt 392 ms 13848 KB
subtask4-27.txt 389 ms 13836 KB
subtask4-28.txt 368 ms 13844 KB
subtask4-29.txt 378 ms 13848 KB
subtask4-30.txt 366 ms 13780 KB