結果

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

---

テストケース

ソースコード

#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;
}