結果

提出番号	1820
提出者	shot
言語	C++
提出日時	2018-08-04 14:05:22
問題名	(73)観光計画
結果	AC
点数	100%

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct Edge {
  int to, cost;
  Edge(int to, int cost) : to(to), cost(cost) {}  
};

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, M, K;
  cin >> N >> M >> K;

  vector<Edge> G[N];
  for ( int i = 0; i < M; i++ ) {
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    G[a].emplace_back(Edge(b, c));    
    G[b].emplace_back(Edge(a, c));    
  }
  
  typedef pair<int, int> P;  
  priority_queue<P> Q;
  for ( int i = 0; i < K; i++ ) {
    int h, d;
    cin >> h >> d;
    h--;
    Q.push({d, h});    
  }

  vector<bool> used(N, false);  
  int ans = 0;
  while ( !Q.empty() ) {
    P p = Q.top(); Q.pop();
    int d = p.first, h = p.second;    

    if ( used[h] ) continue;
    used[h] = true;
    ans++;

    for ( int i = 0; i < (int)G[h].size(); i++ ) {
      Edge u = G[h][i];      
      int to = u.to, cost = u.cost;      
      if ( d-cost < 0 ) continue;
      Q.push({d-cost, to});      
    }    
  }

  cout << ans << endl;
  
  return 0;
}