結果

問題 No.3712 Urban Train
コンテスト
ユーザー flippergo
提出日時 2026-09-19 10:42:56
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 722 ms / 2,000 ms
+ 339µs
コード長 1,125 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,033 ms
コンパイル使用メモリ 80,512 KB
実行使用メモリ 185,552 KB
最終ジャッジ日時 2026-09-19 10:43:07
合計ジャッジ時間 9,379 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq
N,M = map(int,input().split())
A = {}
for _ in range(M):
    u,v,w = map(int,input().split())
    if u>v:
        u,v = v,u
    if (u,v) not in A:
        A[(u,v)] = w
    else:
        if A[(u,v)]>w:
            A[(u,v)] = w
G = {i:[] for i in range(1,N+1)}
for u,v in A:
    G[u].append((v,A[(u,v)]))
    G[v].append((u,A[(u,v)]))
A = [0]+list(map(int,input().split()))
B = [0]+list(map(int,input().split()))
C = [0]+list(map(int,input().split()))
INFTY = 10**15
dist = [INFTY for _ in range(N+1)]
dist[1] = 0
heap = [(0,1)]
visited = [False for _ in range(N+1)]
while heap:
    d,u = heapq.heappop(heap)
    if d>dist[u]:continue
    visited[u] = True
    for v,w in G[u]:
        if visited[v]:continue
        r = d%A[u]
        q = d//A[u]
        t = A[u]-r
        if r>0 or d==0:
            q += 1
        if q%B[u]>0:
            if dist[v]>q*A[u]+w:
                dist[v] = q*A[u]+w
                heapq.heappush(heap,(q*A[u]+w,v))
        else:
            s = q*A[u]+w+min(C[u],A[u])
            if dist[v]>s:
                dist[v] = s
                heapq.heappush(heap,(s,v))
print(dist[N])
0