結果
問題 | No.848 なかよし旅行 |
ユーザー | tobusakana |
提出日時 | 2022-12-01 00:49:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 671 ms / 2,000 ms |
コード長 | 1,824 bytes |
コンパイル時間 | 152 ms |
コンパイル使用メモリ | 82,468 KB |
実行使用メモリ | 114,112 KB |
最終ジャッジ日時 | 2024-04-16 19:04:59 |
合計ジャッジ時間 | 9,109 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 593 ms
113,116 KB |
testcase_01 | AC | 42 ms
53,376 KB |
testcase_02 | AC | 40 ms
52,864 KB |
testcase_03 | AC | 41 ms
53,260 KB |
testcase_04 | AC | 42 ms
52,992 KB |
testcase_05 | AC | 40 ms
53,248 KB |
testcase_06 | AC | 73 ms
72,832 KB |
testcase_07 | AC | 42 ms
53,120 KB |
testcase_08 | AC | 91 ms
76,904 KB |
testcase_09 | AC | 144 ms
78,088 KB |
testcase_10 | AC | 104 ms
76,732 KB |
testcase_11 | AC | 300 ms
87,552 KB |
testcase_12 | AC | 375 ms
91,460 KB |
testcase_13 | AC | 443 ms
96,868 KB |
testcase_14 | AC | 225 ms
80,388 KB |
testcase_15 | AC | 446 ms
96,000 KB |
testcase_16 | AC | 671 ms
114,112 KB |
testcase_17 | AC | 451 ms
100,316 KB |
testcase_18 | AC | 293 ms
85,712 KB |
testcase_19 | AC | 266 ms
84,080 KB |
testcase_20 | AC | 132 ms
78,460 KB |
testcase_21 | AC | 517 ms
105,248 KB |
testcase_22 | AC | 534 ms
113,120 KB |
testcase_23 | AC | 140 ms
77,352 KB |
testcase_24 | AC | 39 ms
52,864 KB |
testcase_25 | AC | 613 ms
109,828 KB |
testcase_26 | AC | 40 ms
52,864 KB |
testcase_27 | AC | 41 ms
52,864 KB |
testcase_28 | AC | 40 ms
52,608 KB |
testcase_29 | AC | 42 ms
52,864 KB |
ソースコード
# P,Qの少なくとも一方に対して往復してもTを越える場合は-1 # P,Q両方に2人とも行って帰ってこれればT # そうでなければ、どこで別れてどこで合流するかを全探索 import sys readline = sys.stdin.readline N,M,P,Q,T = map(int,readline().split()) P -= 1 Q -= 1 G = [[] for i in range(N)] for _ in range(M): a,b,c = map(int,readline().split()) G[a - 1].append([b - 1, c]) G[b - 1].append([a - 1, c]) import heapq as hq INF = 1 << 60 def get_dist(X): res = [INF] * N q = [] hq.heappush(q, (0, X)) while q: d, v = hq.heappop(q) if res[v] != INF: continue res[v] = d for child, c in G[v]: if res[child] != INF: continue hq.heappush(q, (d + c, child)) return res dist_from_0 = get_dist(0) dist_from_P = get_dist(P) dist_from_Q = get_dist(Q) # そもそもかえってこれない if max(dist_from_0[P], dist_from_0[Q]) * 2 > T: print(-1) exit(0) # 両方行ける if dist_from_0[P] + dist_from_P[Q] + dist_from_Q[0] <= T: print(T) exit(0) # そうでない場合、どこかで別れてどこかで合流する。全探索 ans = 0 # 少なくとも別々に行って帰ってこれるので、0は達成できる for i in range(N): for j in range(i, N): P_time = dist_from_P[i] + dist_from_P[j] # Pに寄る人が経由する時間 Q_time = dist_from_Q[i] + dist_from_Q[j] # Q # これらのうち大きい方が、一緒にいられない時間 leave = max(P_time, Q_time) # この二点を経由して帰ってこれるか? if dist_from_0[i] + dist_from_0[j] + leave > T: continue ans = max(ans, T - leave) print(ans)