結果

提出番号	1813
提出者	shot
言語	C++
提出日時	2018-08-04 14:01:23
問題名	(73)観光計画
結果	CE
点数	0%

---

テストケース

ソースコード

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

#define int long long

struct Edge {
  int to, 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});    
  }

  bool used[N] = {};
  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 ( Edge u : G[h] ) {
      int to = u.to, cost = u.cost;      
      if ( d-cost < 0 ) continue;
      Q.push({d-cost, to});      
    }    
  }

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