提出番号 | 2157 |
---|---|

提出者 | Yoshimura |

言語 | C++ |

提出日時 | 2018-08-13 01:36:29 |

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

結果 | WA |

点数 | 0% |

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

1 | WA | 0% | 36ms | 25168KB |

2 | WA | 0% | 43ms | 27008KB |

3 | WA | 0% | 25ms | 19568KB |

4 | WA | 0% | 65ms | 32176KB |

5 | AC | 100% | 30ms | 23328KB |

6 | AC | 100% | 57ms | 30064KB |

7 | WA | 0% | 67ms | 30624KB |

8 | WA | 0% | 68ms | 30176KB |

9 | AC | 100% | 26ms | 22288KB |

10 | WA | 0% | 80ms | 35664KB |

11 | WA | 0% | 40ms | 23728KB |

12 | WA | 0% | 15ms | 17264KB |

13 | WA | 0% | 34ms | 22688KB |

14 | WA | 0% | 73ms | 33472KB |

15 | WA | 0% | 59ms | 27328KB |

16 | WA | 0% | 45ms | 29520KB |

17 | WA | 0% | 73ms | 31680KB |

18 | WA | 0% | 52ms | 26848KB |

19 | WA | 0% | 15ms | 15424KB |

20 | WA | 0% | 39ms | 22720KB |

21 | AC | 100% | 21ms | 20304KB |

22 | WA | 0% | 29ms | 22192KB |

23 | WA | 0% | 30ms | 23280KB |

24 | WA | 0% | 80ms | 37888KB |

25 | WA | 0% | 70ms | 31744KB |

26 | WA | 0% | 79ms | 34192KB |

27 | WA | 0% | 21ms | 18608KB |

28 | WA | 0% | 20ms | 18432KB |

29 | WA | 0% | 48ms | 26736KB |

30 | WA | 0% | 39ms | 22112KB |

31 | WA | 0% | 87ms | 35440KB |

32 | WA | 0% | 48ms | 27952KB |

33 | WA | 0% | 13ms | 15840KB |

34 | WA | 0% | 58ms | 32864KB |

35 | WA | 0% | 13ms | 15904KB |

36 | AC | 100% | 49ms | 30704KB |

37 | WA | 0% | 34ms | 22048KB |

38 | WA | 0% | 10ms | 14880KB |

39 | WA | 0% | 74ms | 37760KB |

40 | WA | 0% | 13ms | 16896KB |

41 | WA | 0% | 79ms | 34368KB |

42 | WA | 0% | 25ms | 18896KB |

43 | WA | 0% | 74ms | 36096KB |

44 | WA | 0% | 42ms | 27072KB |

45 | WA | 0% | 57ms | 27392KB |

46 | WA | 0% | 58ms | 29312KB |

47 | WA | 0% | 65ms | 36096KB |

48 | WA | 0% | 78ms | 35344KB |

49 | WA | 0% | 47ms | 27344KB |

50 | WA | 0% | 68ms | 31696KB |

51 | WA | 0% | 20ms | 18320KB |

52 | WA | 0% | 44ms | 25424KB |

53 | WA | 0% | 27ms | 19504KB |

54 | AC | 100% | 59ms | 30112KB |

55 | WA | 0% | 15ms | 17520KB |

56 | WA | 0% | 44ms | 26096KB |

57 | WA | 0% | 28ms | 20592KB |

58 | WA | 0% | 30ms | 21888KB |

59 | WA | 0% | 18ms | 16304KB |

60 | WA | 0% | 19ms | 19488KB |

61 | WA | 0% | 35ms | 22000KB |

62 | WA | 0% | 66ms | 31888KB |

63 | WA | 0% | 49ms | 28464KB |

64 | WA | 0% | 71ms | 31824KB |

65 | WA | 0% | 54ms | 30528KB |

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

67 | WA | 0% | 46ms | 23232KB |

68 | WA | 0% | 35ms | 25840KB |

69 | WA | 0% | 107ms | 40816KB |

70 | WA | 0% | 45ms | 28352KB |

```
#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 } );
used[h] = true;
}
while( !pque.empty() )
{
P p = pque.top(); pque.pop();
int dist = p.first, v = p.second;
++ans;
for( auto &e : G[v] )
{
int u = e.first, cost = e.second;
if( !used[u] && dist-cost >= 0 )
{
pque.push( { dist-cost, u } );
used[u] = true;
}
}
}
printf( "%d\n", ans );
return 0;
}
```