結果

問題 No.2366 登校
ユーザー flygonflygon
提出日時 2023-06-30 23:20:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,515 bytes
コンパイル時間 236 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 254,336 KB
最終ジャッジ日時 2024-07-07 22:05:38
合計ジャッジ時間 39,383 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 99 ms
77,184 KB
testcase_01 AC 46 ms
63,232 KB
testcase_02 AC 70 ms
74,496 KB
testcase_03 WA -
testcase_04 AC 45 ms
62,976 KB
testcase_05 AC 54 ms
68,096 KB
testcase_06 AC 87 ms
77,244 KB
testcase_07 AC 96 ms
77,568 KB
testcase_08 AC 115 ms
78,208 KB
testcase_09 AC 105 ms
77,780 KB
testcase_10 AC 80 ms
77,124 KB
testcase_11 AC 61 ms
68,992 KB
testcase_12 AC 2,630 ms
136,320 KB
testcase_13 AC 2,546 ms
135,296 KB
testcase_14 AC 2,595 ms
139,652 KB
testcase_15 AC 2,619 ms
141,440 KB
testcase_16 AC 2,601 ms
132,096 KB
testcase_17 AC 2,627 ms
135,472 KB
testcase_18 AC 3,035 ms
144,152 KB
testcase_19 AC 2,591 ms
135,636 KB
testcase_20 WA -
testcase_21 AC 2,569 ms
140,656 KB
testcase_22 AC 2,182 ms
138,172 KB
testcase_23 AC 1,864 ms
180,432 KB
testcase_24 AC 1,850 ms
180,352 KB
testcase_25 TLE -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(5*10**5)
input = sys.stdin.readline
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
from math import gcd

n,m,k,t = map(int,input().split())
t = min(t, 330)
wonderc = defaultdict()
wonderd = defaultdict()
for i in range(k):
    a,b,c,d = map(int,input().split())
    wonderc[(a,b)] = c
    wonderd[(a,b)] = d
#ダイクストラ法
def dijkstra(s): # sがスタート、nが頂点数
    INF = 10**15
    dist = [[INF]*(510) for i in range(n*m)]
    que = [(0,s,170)]
    dist[s][170] = 0
    while que:
        c,crr,tt = heappop(que)
        x,y = crr//m, crr%m
        # print(x,y,tt)
        if c > dist[crr][tt]: continue
        if (x,y) in wonderc.keys():
            if dist[crr][max(0, tt-wonderc[(x,y)]+1)] > dist[crr][tt]+wonderd[(x,y)]:
                dist[crr][max(0, tt-wonderc[(x,y)]+1)] = dist[crr][tt]+wonderd[(x,y)]
                heappush(que,(dist[crr][max(0, tt-wonderc[(x,y)]+1)],crr, max(0, tt-wonderc[(x,y)]+1)))
        for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
            nx,ny = x+dx,y+dy
            if not(0<=nx<n and 0<= ny<m): continue
            nxt = nx*m + ny
            if dist[crr][tt] < dist[nxt][min(510-1,tt+1)]:
                dist[nxt][min(510-1,tt+1)] = dist[crr][tt]
                heappush(que,(dist[nxt][min(510-1,tt+1)],nxt,min(510-1,tt+1)))
    return dist

d =dijkstra(0)
ans = min(d[-1][:t+170+1])
print(ans) if ans != 10**15 else print(-1)
0