結果

提出番号 2157
提出者 Yoshimura
言語 C++
提出日時 2018-08-13 01:36:29
問題名 (73)観光計画
結果 WA
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 WA 0% 36ms 25168KB
2 WA 0% 43ms 27008KB
3 WA 0% 25ms 19568KB
4 WA 0% 65ms 32176KB
5 AC 100% 30ms 23328KB
6 AC 100% 57ms 30064KB
7 WA 0% 67ms 30624KB
8 WA 0% 68ms 30176KB
9 AC 100% 26ms 22288KB
10 WA 0% 80ms 35664KB
11 WA 0% 40ms 23728KB
12 WA 0% 15ms 17264KB
13 WA 0% 34ms 22688KB
14 WA 0% 73ms 33472KB
15 WA 0% 59ms 27328KB
16 WA 0% 45ms 29520KB
17 WA 0% 73ms 31680KB
18 WA 0% 52ms 26848KB
19 WA 0% 15ms 15424KB
20 WA 0% 39ms 22720KB
21 AC 100% 21ms 20304KB
22 WA 0% 29ms 22192KB
23 WA 0% 30ms 23280KB
24 WA 0% 80ms 37888KB
25 WA 0% 70ms 31744KB
26 WA 0% 79ms 34192KB
27 WA 0% 21ms 18608KB
28 WA 0% 20ms 18432KB
29 WA 0% 48ms 26736KB
30 WA 0% 39ms 22112KB
31 WA 0% 87ms 35440KB
32 WA 0% 48ms 27952KB
33 WA 0% 13ms 15840KB
34 WA 0% 58ms 32864KB
35 WA 0% 13ms 15904KB
36 AC 100% 49ms 30704KB
37 WA 0% 34ms 22048KB
38 WA 0% 10ms 14880KB
39 WA 0% 74ms 37760KB
40 WA 0% 13ms 16896KB
41 WA 0% 79ms 34368KB
42 WA 0% 25ms 18896KB
43 WA 0% 74ms 36096KB
44 WA 0% 42ms 27072KB
45 WA 0% 57ms 27392KB
46 WA 0% 58ms 29312KB
47 WA 0% 65ms 36096KB
48 WA 0% 78ms 35344KB
49 WA 0% 47ms 27344KB
50 WA 0% 68ms 31696KB
51 WA 0% 20ms 18320KB
52 WA 0% 44ms 25424KB
53 WA 0% 27ms 19504KB
54 AC 100% 59ms 30112KB
55 WA 0% 15ms 17520KB
56 WA 0% 44ms 26096KB
57 WA 0% 28ms 20592KB
58 WA 0% 30ms 21888KB
59 WA 0% 18ms 16304KB
60 WA 0% 19ms 19488KB
61 WA 0% 35ms 22000KB
62 WA 0% 66ms 31888KB
63 WA 0% 49ms 28464KB
64 WA 0% 71ms 31824KB
65 WA 0% 54ms 30528KB
66 AC 100% 4ms 12976KB
67 WA 0% 46ms 23232KB
68 WA 0% 35ms 25840KB
69 WA 0% 107ms 40816KB
70 WA 0% 45ms 28352KB

ソースコード

#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 } );
    used[h] = true;
  }

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

    ++ans;

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

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

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