結果
問題 | No.2366 登校 |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2023-06-30 22:28:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,982 ms / 4,000 ms |
コード長 | 1,331 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 87,248 KB |
実行使用メモリ | 163,340 KB |
最終ジャッジ日時 | 2023-09-03 03:00:11 |
合計ジャッジ時間 | 17,984 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 81 ms
71,140 KB |
testcase_01 | AC | 73 ms
71,480 KB |
testcase_02 | AC | 78 ms
71,584 KB |
testcase_03 | AC | 74 ms
71,372 KB |
testcase_04 | AC | 74 ms
71,288 KB |
testcase_05 | AC | 73 ms
71,480 KB |
testcase_06 | AC | 72 ms
71,356 KB |
testcase_07 | AC | 77 ms
71,160 KB |
testcase_08 | AC | 76 ms
71,340 KB |
testcase_09 | AC | 77 ms
71,340 KB |
testcase_10 | AC | 74 ms
71,284 KB |
testcase_11 | AC | 74 ms
71,180 KB |
testcase_12 | AC | 1,079 ms
107,632 KB |
testcase_13 | AC | 696 ms
103,724 KB |
testcase_14 | AC | 692 ms
103,216 KB |
testcase_15 | AC | 564 ms
103,792 KB |
testcase_16 | AC | 368 ms
100,184 KB |
testcase_17 | AC | 672 ms
105,116 KB |
testcase_18 | AC | 1,052 ms
108,744 KB |
testcase_19 | AC | 798 ms
105,744 KB |
testcase_20 | AC | 540 ms
102,896 KB |
testcase_21 | AC | 675 ms
104,260 KB |
testcase_22 | AC | 926 ms
107,728 KB |
testcase_23 | AC | 871 ms
138,648 KB |
testcase_24 | AC | 873 ms
138,524 KB |
testcase_25 | AC | 2,845 ms
163,340 KB |
testcase_26 | AC | 2,982 ms
162,928 KB |
ソースコード
""" N,M が小さいんだよな つまり、Tが大きい場合は無視で構わない 後は… dp[x][y][T] = x,y に時刻Tで居る為に必要な最小コスト で良いか 時刻は, T-(N-1-M-1) -200 ~ T 位まで考慮しておけばいいかな """ import sys from sys import stdin import heapq N,M,K,T = map(int,stdin.readline().split()) AB_to_CD = [[None] * M for i in range(N)] for i in range(K): A,B,C,D = map(int,stdin.readline().split()) A -= 1 B -= 1 AB_to_CD[A][B] = (C,D) dp = [[[float("inf")] * 500 for i in range(M)] for j in range(N)] dp[0][0][0] = 0 q = [ (0,0,0,0) ] while q: cost,x,y,t = heapq.heappop(q) if (x,y) == (N-1,M-1) and t <= T: print (cost) sys.exit() if dp[x][y][t] != cost: continue if t <= N+M+10: for nx,ny in ( (x+1,y),(x-1,y),(x,y-1),(x,y+1) ): if 0 <= nx < N and 0 <= ny < M and dp[nx][ny][t+1] > dp[x][y][t]: dp[nx][ny][t+1] = dp[x][y][t] heapq.heappush( q,(dp[nx][ny][t+1] , nx , ny , t+1) ) if AB_to_CD[x][y] != None: C,D = AB_to_CD[x][y] nexT = max(-200 , t-C+1) if dp[x][y][nexT] > D + dp[x][y][t]: dp[x][y][nexT] = D + dp[x][y][t] heapq.heappush( q,(dp[x][y][nexT] , x , y , nexT) ) print (-1)