提出番号 | 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;
}
```