結果

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

---

テストケース

ソースコード

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

typedef pair<int,int> P;

int N, M, K, maxcost[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;
    
    if( maxcost[node] > cost ) continue;
    
    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;
      
      if( maxcost[nnode] < ncost ){
	maxcost[nnode] = ncost;
	Q.push(P( ncost, nnode ));
      }
      
    }
    
  }
  
  int ans = 0;

  for(int i=0;i<N;i++) ans += maxcost[i] != -1;
  
  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 ));
  }
    
  memset( maxcost, -1, sizeof( maxcost ) );
  
  for(int i=0;i<K;i++){
    int h, d;
    cin>>h>>d;
    maxcost[h-1] = max( maxcost[h-1], d );
    Q.push(P( d, h - 1 ));
  }
  
  solve();
  
  return 0;
}