結果

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

---

テストケース

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<queue>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)

int main(){

  struct Edge{
    int to, cost;
    Edge(int t, int c): to(t), cost(c){}
  };

  int n, m, k; cin>> n>> m>> k;
  vector<vector<Edge>> g(n+1);
  rep(i, m){
    int a, b, c; cin>> a>> b>> c;
    a--; b--;
    g[a].push_back(Edge{b, c});
    g[b].push_back(Edge{a, c});
  }
  vector<int> h(k), d(k);
  rep(i, k) cin>> h[i]>> d[i];

  int mxd=*max_element(d.begin(), d.end());
  rep(i, k) g[n].push_back(Edge{h[i]-1, mxd-d[i]});
  using i64=long long;
  i64 inf=1e18;
  vector<i64> dist(n+1, inf);
  struct P{
    int v; i64 d;
    P(int v, i64 d): v(v), d(d){}
    bool operator<(const P &r)const{
      return d>r.d;
    }
  };
  priority_queue<P> q;
  q.push(P{n, 0}); dist[n]=0;
  while(q.size()>0){
    auto p=q.top(); q.pop();
    for(auto e: g[p.v]){
      if(dist[p.v]+e.cost<dist[e.to]){
        dist[e.to]=dist[p.v]+e.cost;
        q.push(P{e.to, dist[e.to]});
      }
    }
  }
  auto count=[&](){
    int cnt=0;
    rep(i, n)if(dist[i]<=mxd) cnt++;
    return cnt;
  };

  cout<< count()<< endl;
  return 0;
}