結果

提出番号	1657
提出者	beet
言語	C++
提出日時	2018-08-04 13:23:34
問題名	(73)観光計画
結果	AC
点数	100%

---

テストケース

ソースコード

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

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,m,k;
  cin>>n>>m>>k;
  using P = pair<Int, Int>;
  vector<vector<P> > G(n);
  for(Int i=0;i<m;i++){
    Int a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    G[a].emplace_back(b,c);
    G[b].emplace_back(a,c);    
  }
  
  vector<Int> dp(n,-1);
  for(Int i=0;i<k;i++){
    Int x,y;
    cin>>x>>y;
    x--;
    chmax(dp[x],y);
  }
  
  priority_queue<P> pq;
  for(Int i=0;i<n;i++){
    if(!dp[i]) continue;
    pq.emplace(dp[i],i);
  }

  while(!pq.empty()){
    Int d,v;
    tie(d,v)=pq.top();pq.pop();
    if(d<dp[v]) continue;
    for(P e:G[v]){
      Int u,c;
      tie(u,c)=e;
      if(dp[u]<dp[v]-c){
	dp[u]=dp[v]-c;
	pq.emplace(dp[u],u);
      }
    }    
  }
  
  Int ans=0;
  for(Int i=0;i<n;i++) ans+=dp[i]>=0;
  cout<<ans<<endl;
  return 0;
}