結果

問題 No.1283 Extra Fee
ユーザー taiga000629taiga000629
提出日時 2020-11-06 23:17:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,446 bytes
コンパイル時間 456 ms
コンパイル使用メモリ 86,876 KB
実行使用メモリ 115,012 KB
最終ジャッジ日時 2023-09-29 19:35:23
合計ジャッジ時間 6,072 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
71,716 KB
testcase_01 AC 90 ms
71,600 KB
testcase_02 AC 94 ms
72,340 KB
testcase_03 AC 90 ms
71,496 KB
testcase_04 AC 93 ms
71,604 KB
testcase_05 AC 94 ms
71,648 KB
testcase_06 AC 97 ms
72,124 KB
testcase_07 AC 97 ms
72,284 KB
testcase_08 AC 162 ms
78,188 KB
testcase_09 AC 113 ms
76,844 KB
testcase_10 AC 101 ms
72,132 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,m=map(int,input().split())
from collections import deque
dp=[[[10**18,10**18] for i in range(n+10)] for j in range(n+10)]
dp[1][1][0]=0
seki=[[0]*(n+10) for i in range(n+10)]

for i in range(m):
    h,w,c=map(int,input().split())
    seki[h][w]=c

data=deque([[1,1]])
while len(data)>0:
    now=data.pop()
    h,w=now[0],now[1]
    if 2<=h:
        f=0
        if seki[h-1][w]==0:
            if dp[h-1][w][0]>dp[h][w][0]+1:
                dp[h-1][w][0]=dp[h][w][0]+1
                f=1
            if dp[h-1][w][1]>dp[h][w][1]+1:
                dp[h-1][w][1]=dp[h][w][1]+1
                f=1
        else:
            if dp[h-1][w][0]>dp[h][w][0]+1+seki[h-1][w]:
                dp[h-1][w][0]=dp[h][w][0]+1+seki[h-1][w]
                f=1
            if dp[h-1][w][1]>dp[h][w][1]+1+seki[h-1][w]:
                dp[h-1][w][1]=dp[h][w][1]+1+seki[h-1][w]
                f=1

            if dp[h-1][w][1]>dp[h][w][0]+1:
                dp[h-1][w][1]=dp[h][w][0]+1
                f=1
        if f:
            data.append([h-1,w])

    if 2 <= w:
        f = 0
        if seki[h ][w-1] == 0:
            if dp[h ][w-1][0] > dp[h][w][0] + 1:
                dp[h ][w-1][0] = dp[h][w][0] + 1
                f = 1
            if dp[h ][w-1][1] > dp[h][w][1] + 1:
                dp[h ][w-1][1] = dp[h][w][1] + 1
                f = 1
        else:
            if dp[h ][w-1][0] > dp[h][w][0] + 1 + seki[h ][w-1]:
                dp[h ][w-1][0] = dp[h][w][0] + 1 + seki[h ][w-1]
                f = 1
            if dp[h ][w-1][1] > dp[h][w][1] + 1 + seki[h ][w-1]:
                dp[h ][w-1][1] = dp[h][w][1] + 1 + seki[h ][w-1]
                f = 1

            if dp[h ][w-1][1] > dp[h][w][0] + 1:
                dp[h ][w-1][1] = dp[h][w][0] + 1
                f = 1
        if f:
            data.append([h , w-1])

    if  h<=n-1:
        f = 0
        if seki[h + 1][w] == 0:
            if dp[h + 1][w][0] > dp[h][w][0] + 1:
                dp[h + 1][w][0] = dp[h][w][0] + 1
                f = 1
            if dp[h + 1][w][1] > dp[h][w][1] + 1:
                dp[h + 1][w][1] = dp[h][w][1] + 1
                f = 1
        else:
            if dp[h + 1][w][0] > dp[h][w][0] + 1 + seki[h + 1][w]:
                dp[h + 1][w][0] = dp[h][w][0] + 1 + seki[h + 1][w]
                f = 1
            if dp[h + 1][w][1] > dp[h][w][1] + 1 + seki[h + 1][w]:
                dp[h + 1][w][1] = dp[h][w][1] + 1 + seki[h + 1][w]
                f = 1

            if dp[h + 1][w][1] > dp[h][w][0] + 1:
                dp[h + 1][w][1] = dp[h][w][0] + 1
                f = 1
        if f:
            data.append([h + 1, w])

    if n-1>=w:
        f = 0
        if seki[h ][w+1] == 0:
            if dp[h ][w+1][0] > dp[h][w][0] + 1:
                dp[h ][w+1][0] = dp[h][w][0] + 1
                f = 1
            if dp[h ][w+1][1] > dp[h][w][1] + 1:
                dp[h ][w+1][1] = dp[h][w][1] + 1
                f = 1
        else:
            if dp[h ][w+1][0] > dp[h][w][0] + 1 + seki[h ][w+1]:
                dp[h ][w+1][0] = dp[h][w][0] + 1 + seki[h ][w+1]
                f = 1
            if dp[h ][w+1][1] > dp[h][w][1] + 1 + seki[h ][w+1]:
                dp[h ][w+1][1] = dp[h][w][1] + 1 + seki[h ][w+1]
                f = 1

            if dp[h ][w+1][1] > dp[h][w][0] + 1:
                dp[h ][w+1][1] = dp[h][w][0] + 1
                f = 1
        if f:
            data.append([h , w+1])

print(min(dp[n][n]))
0