結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2022-05-03 10:57:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 65 ms / 5,000 ms |
コード長 | 989 bytes |
コンパイル時間 | 569 ms |
コンパイル使用メモリ | 82,420 KB |
実行使用メモリ | 71,040 KB |
最終ジャッジ日時 | 2024-07-02 12:59:47 |
合計ジャッジ時間 | 3,879 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
def one_str(): return input() def many_int(): return list(map(int, input().split())) import heapq input_count = 0 N = int(input()) C = int(input()) V = int(input()) S = many_int() T = many_int() Y = many_int() M = many_int() G = {i:[] for i in range(N)} temp_G = {i:set([]) for i in range(N)} for i in range(V): temp_G[S[i]-1].add(f"{T[i]-1}_{M[i]}_{Y[i]}") for k, v in temp_G.items(): for vv in v: t,m,y = vv.split("_") G[k].append((int(t), int(m), int(y))) G q = [[0,0,0]] mins = 10**10 while q: all_minute, all_cost, now_node = heapq.heappop(q) if now_node == (N-1): mins = min(mins, all_minute) break continue for next_node, next_minute, next_cost in G[now_node]: if (all_cost + next_cost) > C: continue else: heapq.heappush(q, (all_minute+next_minute, all_cost+next_cost, next_node)) if mins == 10**10: print(-1) else: print(mins)