結果

提出番号 2362
提出者 kya
言語 C++
提出日時 2020-04-27 17:41:29
問題名 (73)観光計画
結果 WA
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 WA 0% 130ms 33088KB
2 WA 0% 220ms 38352KB
3 WA 0% 67ms 22240KB
4 AC 100% 213ms 47328KB
5 AC 100% 140ms 28400KB
6 AC 100% 171ms 42944KB
7 WA 0% 201ms 49200KB
8 WA 0% 182ms 50240KB
9 AC 100% 101ms 25424KB
10 WA 0% 238ms 61104KB
11 WA 0% 114ms 29696KB
12 WA 0% 40ms 17104KB
13 WA 0% 95ms 31776KB
14 WA 0% 239ms 51840KB
15 WA 0% 155ms 43184KB
16 AC 100% 162ms 40752KB
17 WA 0% 210ms 55200KB
18 WA 0% 199ms 38960KB
19 WA 0% 40ms 21440KB
20 WA 0% 115ms 33280KB
21 AC 100% 65ms 21248KB
22 WA 0% 99ms 27824KB
23 WA 0% 102ms 29376KB
24 WA 0% 257ms 66032KB
25 WA 0% 198ms 53536KB
26 WA 0% 222ms 54864KB
27 WA 0% 54ms 19472KB
28 WA 0% 59ms 18048KB
29 AC 100% 134ms 36512KB
30 WA 0% 95ms 34832KB
31 WA 0% 261ms 60736KB
32 AC 100% 148ms 37824KB
33 WA 0% 31ms 13104KB
34 AC 100% 225ms 49520KB
35 WA 0% 29ms 13024KB
36 WA 0% 174ms 48064KB
37 WA 0% 94ms 26112KB
38 WA 0% 23ms 10032KB
39 WA 0% 283ms 60544KB
40 WA 0% 32ms 16368KB
41 WA 0% 225ms 53616KB
42 WA 0% 61ms 20816KB
43 WA 0% 271ms 62000KB
44 WA 0% 141ms 37824KB
45 WA 0% 174ms 42736KB
46 WA 0% 182ms 42352KB
47 WA 0% 235ms 55568KB
48 WA 0% 238ms 55424KB
49 AC 100% 134ms 35808KB
50 WA 0% 187ms 48192KB
51 WA 0% 52ms 17200KB
52 WA 0% 118ms 32512KB
53 WA 0% 74ms 22384KB
54 AC 100% 167ms 42192KB
55 WA 0% 44ms 17904KB
56 WA 0% 142ms 38016KB
57 WA 0% 71ms 31696KB
58 WA 0% 99ms 29376KB
59 WA 0% 52ms 23520KB
60 WA 0% 61ms 21472KB
61 WA 0% 94ms 26960KB
62 AC 100% 211ms 47328KB
63 WA 0% 168ms 45536KB
64 WA 0% 198ms 51216KB
65 WA 0% 186ms 46272KB
66 WA 0% 5ms 8672KB
67 WA 0% 111ms 35408KB
68 WA 0% 132ms 37584KB
69 WA 0% 288ms 72800KB
70 WA 0% 161ms 39856KB

ソースコード

#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(), -1);
    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(ret[s], s); ret[s] = 0;
    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 or ret[e.to] == -1) {
                ret[e.to] = ret[v] + e.cost;
                que.emplace(ret[e.to], e.to);
            }
        }
    }
    return ret;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    Graph<long long> g(n + 1);
    
    for (int i = 0; i < m; i++) {
        int a, b, 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, 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++) {
        ans += (dist[i] <= 0);
    }
    
    cout << ans << '\n';
    
    return 0;
}