結果

提出番号	2363
提出者	kya
言語	C++
提出日時	2020-04-27 17:54:38
問題名	(73)観光計画
結果	AC
点数	100%

---

テストケース

ソースコード

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

template<typename T> struct Edge {
    int to; T cost;
    Edge (int to, T cost = 1) : to(to), cost(cost) { }
    bool operator< (const Edge &r) const { return (cost < r.cost); }
};

template<typename T> using Graph = vector<vector<Edge<T>>>;

template <typename T> vector<T> dijkstra(const Graph<T> &g, int s) {
    using P = pair<T, int>;
    vector<T> ret(g.size(), numeric_limits<T>::max()); ret[s] = 0;
    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(ret[s], s);
    while (not que.empty()) {
        int v; T c; tie(c, v) = que.top(); que.pop();
        if (ret[v] < c) continue;
        for (const auto &e : g[v]) {
            if (ret[e.to] > ret[v] + e.cost) {
                ret[e.to] = ret[v] + e.cost;
                que.emplace(ret[e.to], e.to);
            }
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    Graph<long long> g(n + 1);
    
    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    
    for (int i = 0; i < k; i++) {
        int id;
        long long d;
        cin >> id >> d;
        g[0].emplace_back(id, -d);
    }
    
    vector<long long> dist = dijkstra(g, 0);
    
    int ans = 0;
    for (int i = 1; i < n + 1; i++) {
        if (dist[i] <= 0) ans++;
    }
    
    cout << ans << '\n';
    
    return 0;
}