結果

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

---

テストケース

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
  ll to,cost;
  edge(ll to,ll cost) : to(to), cost(cost) {}
};

ll N,M,K;
vector< ll > d,h;
vector< edge > G[100005];


int main(){
  cin>>N>>M>>K;
  for(int i=0;i<M;i++){
    ll a,b,c;
    cin>>a>>b>>c;
    a--,b--;
    G[a].push_back( edge(b,c) );
    G[b].push_back( edge(a,c) );
  }
  
  h.resize(K);
  d.resize(K);

  const ll tmp = (1LL<<30);
  
  for(int i=0;i<K;i++){
    cin>>h[i]>>d[i];
    h[i]--;

    G[ N ].push_back( (edge){ h[i], tmp - d[i] } );
  }

  vector<ll> dist( N+1 , (1LL<<60) );
  dist[ N ] = 0;
  typedef pair<ll,ll> P;
  priority_queue< P , vector<P> , greater<P> > Q;
  Q.push( P(0,N) );
  while(!Q.empty()){
    P p=Q.top();
    Q.pop();
    ll pos=p.second;
    ll cost=p.first;
    if( dist[pos] < cost )continue;
    for(int i=0;i<(int)G[pos].size();i++){
      edge e=G[pos][i];
      if( cost + e.cost < dist[ e.to ] ){
        dist[ e.to ] = cost + e.cost;
        Q.push( P( dist[e.to] , e.to ) );
      }
    }
  }

  ll ans=0;
  for(int i=0;i<N;i++)
    if( dist[i] <= tmp )ans++;
  cout<<ans<<endl;
  return 0;
}