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