結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2014-11-05 23:37:29 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 35 ms / 5,000 ms |
コード長 | 1,083 bytes |
コンパイル時間 | 128 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-07-20 16:06:00 |
合計ジャッジ時間 | 2,538 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
import sys #sys.setrecursionlimit(n) import heapq import re import bisect from collections import defaultdict, deque n = int(input()) c = int(input()) v = int(input()) s = tuple(map(int, input().split())) t = tuple(map(int, input().split())) y = tuple(map(int, input().split())) m = tuple(map(int, input().split())) d = defaultdict(lambda : defaultdict(list)) for i in range(v): d[s[i]][t[i]].append((m[i] << 16) + y[i]) def solve(): heap = [] heapq.heappush(heap, (0 << 32) + (0 << 16) + 1) while (heap): h = heapq.heappop(heap) hm = (h >> 32) & 0xFFFFFFFF hcost = (h >> 16) & 0xFFFF hpos = h & 0xFFFF if hpos == n: return hm else: for dd in d[hpos]: for td in d[hpos][dd]: nextcost = (td & 0xFFFF) + hcost nexthm = ((td >> 16) & 0xFFFFFFFF) + hm if nextcost <= c: heapq.heappush(heap, (nexthm << 32) + (nextcost << 16) + dd) return -1 print(solve())