結果

提出番号	1997
提出者	Gacho_0716
言語	C++
提出日時	2018-08-04 14:52:00
問題名	(73)観光計画
結果	TLE
点数	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;
    
    used[node] = 1;
    
    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 ) continue;
      
      Q.push(P( ncost, nnode ));
      
    }
    
  }
  
  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 ));
  }
  
  solve();
  
  return 0;
}