結果

問題 No.1283 Extra Fee
コンテスト
ユーザー taiga000629
提出日時 2020-11-06 23:17:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,446 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 114,232 KB
最終ジャッジ日時 2024-07-22 13:39:41
合計ジャッジ時間 5,158 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

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