結果

提出番号	1960
提出者	Gacho_0716
言語	C++
提出日時	2018-08-04 14:44:49
問題名	(73)観光計画
結果	WA
点数	0%

---

テストケース

ソースコード

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

typedef pair<int,int> P;

int N, M, K, used[100005];
vector<P> G[100005];
priority_queue<P> Q;

void solve(){
  
  while(!Q.empty()){
    
    P t = Q.top(); Q.pop();
    
    int node = t.second;
    int cost = t.first;
    
    for(int i=0;i<(int)G[node].size();i++){
      
      int nnode = G[node][i].first;
      int ncost = cost - G[node][i].second;
      
      if( ncost < 0 || used[nnode] == 1 ) continue;

      Q.push(P( ncost, nnode ));
      used[nnode] = 1;
      
    }
    
  }

  int ans = 0;

  for(int i=0;i<N;i++) ans += used[i];
  
  cout<<ans<<endl;
  
}

signed main(){
  
  cin>>N>>M>>K;
  
  for(int i=0;i<M;i++){
    int a, b, c;
    cin>>a>>b>>c;
    G[a-1].push_back(P( b-1, c ));
    G[b-1].push_back(P( a-1, c ));
  }
  
  for(int i=0;i<K;i++){
    int h, d;
    cin>>h>>d;
    Q.push(P( d, h - 1 ));
    used[h-1] = 1;
  }
  
  solve();
  
  return 0;
}