提出番号 | 2158 |
---|---|

提出者 | Yoshimura |

言語 | C++ |

提出日時 | 2018-08-13 01:40:05 |

問題名 | (73)観光計画 |

結果 | AC |

点数 | 100% |

テストケース | 結果 | 得点 | 実行時間 | メモリ使用量 |
---|---|---|---|---|

1 | AC | 100% | 57ms | 27776KB |

2 | AC | 100% | 65ms | 27744KB |

3 | AC | 100% | 26ms | 19568KB |

4 | AC | 100% | 82ms | 34752KB |

5 | AC | 100% | 49ms | 26448KB |

6 | AC | 100% | 65ms | 32512KB |

7 | AC | 100% | 64ms | 32800KB |

8 | AC | 100% | 64ms | 30176KB |

9 | AC | 100% | 46ms | 25792KB |

10 | AC | 100% | 85ms | 35200KB |

11 | AC | 100% | 38ms | 25168KB |

12 | AC | 100% | 14ms | 17264KB |

13 | AC | 100% | 32ms | 22416KB |

14 | AC | 100% | 97ms | 36144KB |

15 | AC | 100% | 61ms | 28944KB |

16 | AC | 100% | 63ms | 32384KB |

17 | AC | 100% | 88ms | 30464KB |

18 | AC | 100% | 65ms | 29232KB |

19 | AC | 100% | 13ms | 15312KB |

20 | AC | 100% | 37ms | 24336KB |

21 | AC | 100% | 29ms | 22240KB |

22 | AC | 100% | 37ms | 22720KB |

23 | AC | 100% | 31ms | 23536KB |

24 | AC | 100% | 92ms | 39984KB |

25 | AC | 100% | 84ms | 30544KB |

26 | AC | 100% | 98ms | 36480KB |

27 | AC | 100% | 19ms | 18464KB |

28 | AC | 100% | 21ms | 18528KB |

29 | AC | 100% | 52ms | 29360KB |

30 | AC | 100% | 34ms | 22240KB |

31 | AC | 100% | 92ms | 37104KB |

32 | AC | 100% | 57ms | 30912KB |

33 | AC | 100% | 14ms | 15776KB |

34 | AC | 100% | 96ms | 35488KB |

35 | AC | 100% | 14ms | 15968KB |

36 | AC | 100% | 47ms | 30688KB |

37 | AC | 100% | 34ms | 23072KB |

38 | AC | 100% | 11ms | 15264KB |

39 | AC | 100% | 109ms | 39456KB |

40 | AC | 100% | 11ms | 16912KB |

41 | AC | 100% | 86ms | 37040KB |

42 | AC | 100% | 22ms | 18800KB |

43 | AC | 100% | 118ms | 42000KB |

44 | AC | 100% | 58ms | 28144KB |

45 | AC | 100% | 75ms | 29664KB |

46 | AC | 100% | 75ms | 31920KB |

47 | AC | 100% | 99ms | 38720KB |

48 | AC | 100% | 106ms | 42112KB |

49 | AC | 100% | 55ms | 30208KB |

50 | AC | 100% | 64ms | 32272KB |

51 | AC | 100% | 18ms | 18416KB |

52 | AC | 100% | 50ms | 26720KB |

53 | AC | 100% | 26ms | 19872KB |

54 | AC | 100% | 81ms | 37424KB |

55 | AC | 100% | 16ms | 17520KB |

56 | AC | 100% | 44ms | 26560KB |

57 | AC | 100% | 27ms | 20416KB |

58 | AC | 100% | 33ms | 21792KB |

59 | AC | 100% | 19ms | 16496KB |

60 | AC | 100% | 23ms | 19504KB |

61 | AC | 100% | 33ms | 22768KB |

62 | AC | 100% | 92ms | 38720KB |

63 | AC | 100% | 52ms | 29968KB |

64 | AC | 100% | 94ms | 34176KB |

65 | AC | 100% | 85ms | 33200KB |

66 | AC | 100% | 4ms | 12992KB |

67 | AC | 100% | 42ms | 24848KB |

68 | AC | 100% | 36ms | 25152KB |

69 | AC | 100% | 129ms | 44464KB |

70 | AC | 100% | 55ms | 29408KB |

```
#include <cstdio>
#include <vector>
#include <queue>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()
constexpr int MAX_N = 100010;
using P = std::pair<int, int>;
int N, M, K;
std::vector<P> G[MAX_N];
std::priority_queue<P> pque;
bool used[MAX_N];
int ans;
int main()
{
scanf( "%d%d%d", &N, &M, &K );
rep( i, M )
{
int a, b, c;
scanf( "%d%d%d", &a, &b, &c );
--a; --b;
G[a].push_back( { b, c } );
G[b].push_back( { a, c } );
}
rep( i, K )
{
int h, d;
scanf( "%d%d", &h, &d );
--h;
pque.push( { d, h } );
}
while( !pque.empty() )
{
P p = pque.top(); pque.pop();
int dist = p.first, v = p.second;
if( used[v] )
continue;
used[v] = true;
++ans;
for( auto &e : G[v] )
{
int u = e.first, cost = e.second;
if( !used[u] && dist-cost >= 0 )
pque.push( { dist-cost, u } );
}
}
printf( "%d\n", ans );
return 0;
}
```