結果

問題 No.1995 CHIKA Road
ユーザー 学ぶマン
提出日時 2025-10-15 22:48:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,048 bytes
コンパイル時間 341 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 146,940 KB
最終ジャッジ日時 2025-10-15 22:48:52
合計ジャッジ時間 29,356 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

INF = 10**18
from collections import defaultdict
N, M = map(int, input().split())
G = defaultdict(list)
events = []

def chmax(DP,i,v):
    if DP[i] < v: DP[i] = v
def chmin(DP,i,v):
    if DP[i] > v: DP[i] = v

for i in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    events.append(a)
    events.append(b)

events.sort()
if N not in events:
    events.append(N)

dp = defaultdict(lambda: INF)
dp[1] = 0
# 確定マスのうち一番大きいもの
pre = 1

for masu in events:

    # pre から近道無しで来た場合
    option1 = dp[pre] + (masu - pre)*2
    #option2 = INF

    # 近道で masu まで来る経路がある場合
    #if masu in dp:
    #    option2 = dp[masu]
    
    #dp[masu] = min(option1, option2)
    chmin(dp, masu, option1)


    # 近道で このさきのマスへの経路がある場合は蒔いておく
    for nex in G[masu]:
        # dp[nex] = min(dp[nex], dp[masu] + (2*nex - 2*masu - 1)
        chmin(dp, nex, dp[masu] + (2*nex - 2*masu - 1))

    pre = masu

ans = dp[N]
print(ans)
0