結果

問題 No.2366 登校
ユーザー titiatitia
提出日時 2023-07-01 02:29:50
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,116 bytes
コンパイル時間 250 ms
コンパイル使用メモリ 86,796 KB
実行使用メモリ 186,936 KB
最終ジャッジ日時 2023-09-22 17:42:05
合計ジャッジ時間 39,067 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 160 ms
78,100 KB
testcase_01 AC 78 ms
71,160 KB
testcase_02 AC 95 ms
76,120 KB
testcase_03 AC 164 ms
79,164 KB
testcase_04 AC 79 ms
71,108 KB
testcase_05 AC 119 ms
77,376 KB
testcase_06 AC 163 ms
78,988 KB
testcase_07 AC 187 ms
79,324 KB
testcase_08 AC 214 ms
79,916 KB
testcase_09 AC 212 ms
80,052 KB
testcase_10 AC 103 ms
76,284 KB
testcase_11 AC 136 ms
78,072 KB
testcase_12 AC 2,771 ms
118,792 KB
testcase_13 AC 2,554 ms
116,256 KB
testcase_14 AC 2,600 ms
118,616 KB
testcase_15 AC 2,698 ms
121,056 KB
testcase_16 AC 2,658 ms
115,568 KB
testcase_17 AC 2,686 ms
118,372 KB
testcase_18 AC 2,592 ms
121,204 KB
testcase_19 AC 2,626 ms
118,008 KB
testcase_20 AC 2,688 ms
119,952 KB
testcase_21 AC 2,559 ms
117,544 KB
testcase_22 AC 2,175 ms
118,704 KB
testcase_23 AC 1,124 ms
115,036 KB
testcase_24 AC 1,068 ms
115,064 KB
testcase_25 TLE -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from heapq import heappop,heappush

N,M,K,T=map(int,input().split())

X=[[(-1,-1)]*M for i in range(N)]

for i in range(K):
    a,b,c,d=map(int,input().split())
    a-=1
    b-=1
    X[a][b]=[c,d]

DP=[[[1<<63]*M for i in range(N)] for j in range(400)]

Q=[(0,0,0,0)]
DP[200][0][0]=0

while Q:
    now,x,y,time=heappop(Q)
    if DP[time+200][x][y]!=now:
        continue

    for z,w in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
        if 0<=z<N and 0<=w<M and 0<=time+1+200<400 and DP[time+1+200][z][w]>now:
            DP[time+1+200][z][w]=now
            heappush(Q,(DP[time+1+200][z][w],z,w,time+1))

    if X[x][y]!=(-1,-1):
        c,d=X[x][y]
        if 0<=time-c+1+200<400 and DP[time-c+1+200][x][y]>now+d:
            DP[time-c+1+200][x][y]=now+d
            heappush(Q,(DP[time-c+1+200][x][y],x,y,time-c+1))
        elif time-c+1+200<0 and DP[0][x][y]>now+d:
            DP[0][x][y]=now+d
            heappush(Q,(DP[0][x][y],x,y,-200))

ANS=1<<63

for i in range(400):
    if i-200<=T:
        ANS=min(ANS,DP[i][N-1][M-1])

if ANS>=1<<60:
    print(-1)
else:
    print(ANS)
0