結果

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

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 61ms 33152KB
2 AC 100% 66ms 38464KB
3 AC 100% 32ms 22336KB
4 AC 100% 80ms 47408KB
5 AC 100% 45ms 28512KB
6 AC 100% 68ms 42992KB
7 AC 100% 89ms 49280KB
8 AC 100% 86ms 50336KB
9 AC 100% 38ms 25344KB
10 AC 100% 106ms 61200KB
11 AC 100% 49ms 29792KB
12 AC 100% 19ms 17200KB
13 AC 100% 45ms 31872KB
14 AC 100% 95ms 51936KB
15 AC 100% 87ms 43264KB
16 AC 100% 70ms 40880KB
17 AC 100% 92ms 55296KB
18 AC 100% 74ms 39056KB
19 AC 100% 20ms 21520KB
20 AC 100% 58ms 33376KB
21 AC 100% 23ms 21200KB
22 AC 100% 47ms 27952KB
23 AC 100% 51ms 29472KB
24 AC 100% 135ms 66112KB
25 AC 100% 97ms 53616KB
26 AC 100% 123ms 54944KB
27 AC 100% 26ms 19568KB
28 AC 100% 26ms 18160KB
29 AC 100% 58ms 36592KB
30 AC 100% 52ms 34928KB
31 AC 100% 125ms 60848KB
32 AC 100% 60ms 37920KB
33 AC 100% 16ms 13184KB
34 AC 100% 95ms 49632KB
35 AC 100% 16ms 13120KB
36 AC 100% 91ms 48160KB
37 AC 100% 42ms 26224KB
38 AC 100% 10ms 10304KB
39 AC 100% 132ms 60624KB
40 AC 100% 16ms 15920KB
41 AC 100% 98ms 53712KB
42 AC 100% 30ms 20928KB
43 AC 100% 132ms 62080KB
44 AC 100% 65ms 37920KB
45 AC 100% 82ms 42832KB
46 AC 100% 72ms 42480KB
47 AC 100% 109ms 55680KB
48 AC 100% 115ms 55472KB
49 AC 100% 56ms 36112KB
50 AC 100% 103ms 48272KB
51 AC 100% 26ms 17312KB
52 AC 100% 59ms 32624KB
53 AC 100% 33ms 22480KB
54 AC 100% 66ms 42208KB
55 AC 100% 22ms 18000KB
56 AC 100% 77ms 38112KB
57 AC 100% 35ms 31776KB
58 AC 100% 51ms 29472KB
59 AC 100% 26ms 23616KB
60 AC 100% 32ms 21568KB
61 AC 100% 46ms 27056KB
62 AC 100% 93ms 47424KB
63 AC 100% 77ms 45632KB
64 AC 100% 108ms 51360KB
65 AC 100% 93ms 46368KB
66 AC 100% 4ms 9568KB
67 AC 100% 62ms 35520KB
68 AC 100% 57ms 37680KB
69 AC 100% 141ms 72896KB
70 AC 100% 75ms 39936KB

ソースコード

#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;
}