結果

提出番号	2059
提出者	_ei1333
言語	C++
提出日時	2018-08-04 15:08:02
問題名	(73)観光計画
結果	AC
点数	100%

---

テストケース

ソースコード

#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
#define chmin(a, b) a = min(a, b)
using namespace std;
typedef pair<int, int> P;
const int INF = 1e15;

struct edge{
   int to, cost;
};
int n, m, k;
vector<edge> G[100010]; 
int d[100010];

void dfs(int v, int p, int now){
    if(d[v] > now) return;
    d[v] = now;
    rep(i, 0, G[v].size()){
        int nxtv = G[v][i].to;
        int nxtn = now - G[v][i].cost;
        if(nxtv == p || nxtn < 0) continue;
        dfs(nxtv, v, nxtn);
    }
}

signed main(){
    cin >> n >> m >> k;
    rep(i, 0, m){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    rep(i, 0, n) d[i] = -1;
    vector<P> h(k); 
    rep(i, 0, k){
        cin >> h[i].second >> h[i].first;
        h[i].second--;
    }
    sort(h.rbegin(), h.rend());
    rep(i, 0, k){
        dfs(h[i].second, -1, h[i].first);
    }
    int ans = 0;
    rep(i, 0, n) if(d[i] >= 0) ans++;
    cout << ans << endl;
}