結果

提出番号 2158
提出者 Yoshimura
言語 C++
提出日時 2018-08-13 01:40:05
問題名 (73)観光計画
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 57ms 27776KB
2 AC 100% 65ms 27744KB
3 AC 100% 26ms 19568KB
4 AC 100% 82ms 34752KB
5 AC 100% 49ms 26448KB
6 AC 100% 65ms 32512KB
7 AC 100% 64ms 32800KB
8 AC 100% 64ms 30176KB
9 AC 100% 46ms 25792KB
10 AC 100% 85ms 35200KB
11 AC 100% 38ms 25168KB
12 AC 100% 14ms 17264KB
13 AC 100% 32ms 22416KB
14 AC 100% 97ms 36144KB
15 AC 100% 61ms 28944KB
16 AC 100% 63ms 32384KB
17 AC 100% 88ms 30464KB
18 AC 100% 65ms 29232KB
19 AC 100% 13ms 15312KB
20 AC 100% 37ms 24336KB
21 AC 100% 29ms 22240KB
22 AC 100% 37ms 22720KB
23 AC 100% 31ms 23536KB
24 AC 100% 92ms 39984KB
25 AC 100% 84ms 30544KB
26 AC 100% 98ms 36480KB
27 AC 100% 19ms 18464KB
28 AC 100% 21ms 18528KB
29 AC 100% 52ms 29360KB
30 AC 100% 34ms 22240KB
31 AC 100% 92ms 37104KB
32 AC 100% 57ms 30912KB
33 AC 100% 14ms 15776KB
34 AC 100% 96ms 35488KB
35 AC 100% 14ms 15968KB
36 AC 100% 47ms 30688KB
37 AC 100% 34ms 23072KB
38 AC 100% 11ms 15264KB
39 AC 100% 109ms 39456KB
40 AC 100% 11ms 16912KB
41 AC 100% 86ms 37040KB
42 AC 100% 22ms 18800KB
43 AC 100% 118ms 42000KB
44 AC 100% 58ms 28144KB
45 AC 100% 75ms 29664KB
46 AC 100% 75ms 31920KB
47 AC 100% 99ms 38720KB
48 AC 100% 106ms 42112KB
49 AC 100% 55ms 30208KB
50 AC 100% 64ms 32272KB
51 AC 100% 18ms 18416KB
52 AC 100% 50ms 26720KB
53 AC 100% 26ms 19872KB
54 AC 100% 81ms 37424KB
55 AC 100% 16ms 17520KB
56 AC 100% 44ms 26560KB
57 AC 100% 27ms 20416KB
58 AC 100% 33ms 21792KB
59 AC 100% 19ms 16496KB
60 AC 100% 23ms 19504KB
61 AC 100% 33ms 22768KB
62 AC 100% 92ms 38720KB
63 AC 100% 52ms 29968KB
64 AC 100% 94ms 34176KB
65 AC 100% 85ms 33200KB
66 AC 100% 4ms 12992KB
67 AC 100% 42ms 24848KB
68 AC 100% 36ms 25152KB
69 AC 100% 129ms 44464KB
70 AC 100% 55ms 29408KB

ソースコード

#include <cstdio>
#include <vector>
#include <queue>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

constexpr int MAX_N = 100010;

using P = std::pair<int, int>;

int N, M, K;
std::vector<P> G[MAX_N];
std::priority_queue<P> pque;
bool used[MAX_N];
int ans;

int main()
{
  scanf( "%d%d%d", &N, &M, &K );
  rep( i, M )
  {
    int a, b, c;
    scanf( "%d%d%d", &a, &b, &c );
    --a; --b;
    G[a].push_back( { b, c } );
    G[b].push_back( { a, c } );
  }

  rep( i, K )
  {
    int h, d;
    scanf( "%d%d", &h, &d );
    --h;
    pque.push( { d, h } );
  }

  while( !pque.empty() )
  {
    P p = pque.top(); pque.pop();
    int dist = p.first, v = p.second;

    if( used[v] )
      continue;

    used[v] = true;

    ++ans;

    for( auto &e : G[v] )
    {
      int u = e.first, cost = e.second;

      if( !used[u] && dist-cost >= 0 )
        pque.push( { dist-cost, u } );
    }
  }

  printf( "%d\n", ans );
  
  return 0;
}