結果

問題 No.1283 Extra Fee
コンテスト
ユーザー flippergo
提出日時 2026-07-14 10:15:50
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 891 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 447 ms
コンパイル使用メモリ 95,728 KB
実行使用メモリ 169,140 KB
最終ジャッジ日時 2026-07-14 10:16:04
合計ジャッジ時間 6,032 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq
N,M = map(int,input().split())
C = [[0 for _ in range(N+1)] for _ in range(N+1)]
A = []
for _ in range(M):
    h,w,c = map(int,input().split())
    C[h][w] = c
    A.append((h,w))
INFTY = 10**12+10000
ans = INFTY
for h,w in A:
    c0 = C[h][w]
    C[h][w] = 0
    dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
    dist[1][1] = 0
    visited = [[False for _ in range(N+1)] for _ in range(N+1)]
    heap = [(0,1,1)]
    while heap:
        d,i,j = heapq.heappop(heap)
        if dist[i][j]<d:continue
        visited[i][j] = True
        for di,dj in [[0,1],[-1,0],[0,-1],[1,0]]:
            if 1<=i+di<=N and 1<=j+dj<=N and visited[i+di][j+dj]==False and dist[i+di][j+dj]>d+1+C[i+di][j+dj]:
                dist[i+di][j+dj] = d+1+C[i+di][j+dj]
                heapq.heappush(heap,(d+1+C[i+di][j+dj],i+di,j+dj))
    ans = min(ans,dist[N][N])
    C[h][w] = c0
print(ans)
0