提出番号 | 1791 |
---|---|
提出者 | hamayanhamayan |
言語 | C++ |
提出日時 | 2018-08-04 13:54:27 |
問題名 | (73)観光計画 |
結果 | AC |
点数 | 100% |
テストケース | 結果 | 得点 | 実行時間 | メモリ使用量 |
---|---|---|---|---|
1 | AC | 100% | 61ms | 30128KB |
2 | AC | 100% | 71ms | 30400KB |
3 | AC | 100% | 28ms | 22528KB |
4 | AC | 100% | 80ms | 37088KB |
5 | AC | 100% | 52ms | 28560KB |
6 | AC | 100% | 69ms | 34784KB |
7 | AC | 100% | 82ms | 36016KB |
8 | AC | 100% | 79ms | 33152KB |
9 | AC | 100% | 44ms | 27872KB |
10 | AC | 100% | 125ms | 37392KB |
11 | AC | 100% | 42ms | 27536KB |
12 | AC | 100% | 15ms | 19840KB |
13 | AC | 100% | 32ms | 25392KB |
14 | AC | 100% | 86ms | 38672KB |
15 | AC | 100% | 74ms | 32160KB |
16 | AC | 100% | 67ms | 34592KB |
17 | AC | 100% | 93ms | 33120KB |
18 | AC | 100% | 71ms | 31792KB |
19 | AC | 100% | 16ms | 17376KB |
20 | AC | 100% | 43ms | 26480KB |
21 | AC | 100% | 27ms | 24288KB |
22 | AC | 100% | 41ms | 25232KB |
23 | AC | 100% | 34ms | 26112KB |
24 | AC | 100% | 132ms | 43072KB |
25 | AC | 100% | 91ms | 33488KB |
26 | AC | 100% | 103ms | 38896KB |
27 | AC | 100% | 24ms | 20976KB |
28 | AC | 100% | 21ms | 20672KB |
29 | AC | 100% | 66ms | 31648KB |
30 | AC | 100% | 37ms | 25312KB |
31 | AC | 100% | 139ms | 40384KB |
32 | AC | 100% | 61ms | 33168KB |
33 | AC | 100% | 15ms | 17904KB |
34 | AC | 100% | 96ms | 37872KB |
35 | AC | 100% | 14ms | 18192KB |
36 | AC | 100% | 47ms | 33504KB |
37 | AC | 100% | 43ms | 25504KB |
38 | AC | 100% | 12ms | 17216KB |
39 | AC | 100% | 111ms | 42560KB |
40 | AC | 100% | 13ms | 19456KB |
41 | AC | 100% | 94ms | 39536KB |
42 | AC | 100% | 29ms | 21424KB |
43 | AC | 100% | 129ms | 44704KB |
44 | AC | 100% | 61ms | 30624KB |
45 | AC | 100% | 72ms | 31984KB |
46 | AC | 100% | 68ms | 34352KB |
47 | AC | 100% | 117ms | 41184KB |
48 | AC | 100% | 122ms | 44624KB |
49 | AC | 100% | 64ms | 32432KB |
50 | AC | 100% | 89ms | 34416KB |
51 | AC | 100% | 23ms | 20560KB |
52 | AC | 100% | 55ms | 29072KB |
53 | AC | 100% | 33ms | 22560KB |
54 | AC | 100% | 73ms | 39568KB |
55 | AC | 100% | 20ms | 20016KB |
56 | AC | 100% | 47ms | 29328KB |
57 | AC | 100% | 26ms | 22864KB |
58 | AC | 100% | 42ms | 23824KB |
59 | AC | 100% | 25ms | 19040KB |
60 | AC | 100% | 25ms | 22000KB |
61 | AC | 100% | 43ms | 25344KB |
62 | AC | 100% | 95ms | 41024KB |
63 | AC | 100% | 60ms | 32960KB |
64 | AC | 100% | 101ms | 36608KB |
65 | AC | 100% | 86ms | 35792KB |
66 | AC | 100% | 4ms | 15360KB |
67 | AC | 100% | 57ms | 28016KB |
68 | AC | 100% | 52ms | 28832KB |
69 | AC | 100% | 115ms | 47472KB |
70 | AC | 100% | 58ms | 31808KB |
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
∧_∧
∧_∧ (´<_` ) Welcome to My Coding Space!
( ´_ゝ`) / ⌒i
/ \ | |
/ / ̄ ̄ ̄ ̄/ |
__(__ニつ/ _/ .| .|____
\/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/
int N, M, K;
vector<pair<int, int>> E[101010];
int vis[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> N >> M >> K;
rep(i, 0, M) {
int a, b, c; cin >> a >> b >> c;
a--; b--;
E[a].push_back({ b, c });
E[b].push_back({ a, c });
}
priority_queue<pair<int, int>> que;
rep(i, 0, K) {
int h, d; cin >> h >> d;
h--;
que.push({ d, h });
}
int ans = 0;
while (!que.empty()) {
auto q = que.top();
que.pop();
int cu = q.second;
int rest = q.first;
if (vis[cu]) continue;
vis[cu] = 1;
ans++;
fore(tp, E[cu]) {
int to = tp.first;
int cst = tp.second;
if (vis[to]) continue;
if (0 <= rest - cst) que.push({ rest - cst, to });
}
}
cout << ans << endl;
}