結果

問題 No.3616 WK vs AT vs MT vs SP
コンテスト
ユーザー detteiuu
提出日時 2026-08-08 19:03:24
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 925 ms / 2,000 ms
+ 392µs
コード長 1,712 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 224 ms
コンパイル使用メモリ 95,724 KB
実行使用メモリ 135,464 KB
最終ジャッジ日時 2026-08-08 19:03:45
合計ジャッジ時間 17,093 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 1
小課題1 8 % AC * 9
小課題2 16 % AC * 5
小課題3 20 % AC * 10
小課題4 20 % AC * 15
小課題5 20 % AC * 15
小課題6 16 % AC * 36
合計 2.5 * 100% = 250 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from heapq import heappush, heappop

INF = 1<<60

def encode(n, f):
    return n*6+f
def decode(n):
    return n//6, n%6

N, R, C = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
Z = list(map(int, input().split()))
S = list(map(int, input().split()))
G = [[] for _ in range(N+1)]
for _ in range(R):
    u, v, w, a, m = map(int, input().split())
    u, v = u-1, v-1
    G[u].append((v, w, a, m, INF))
    G[v].append((u, w, a, m, INF))

for i in range(N):
    G[i].append((N, INF, INF, INF, S[i]))
    G[N].append((i, INF, INF, INF, S[i]+C))

dist = [[INF]*6 for _ in range(N+1)]
dist[0][0] = 0
visited = [[False]*6 for _ in range(N+1)]
que = [(0, encode(0, 0))]
while que:
    _, now = heappop(que)
    n, f = decode(now)
    if visited[n][f]:
        continue
    visited[n][f] = True
    for v, w, a, m, s in G[n]:
        d = w
        if 1 <= f%3:
            d = min(d, a)
        if 2 <= f%3:
            d = min(d, m)
        if f//3 == 1:
            d = min(d, s)
        if d == INF: continue
        if dist[n][f]+d < dist[v][f]:
            dist[v][f] = dist[n][f]+d
            heappush(que, (dist[v][f], encode(v, f)))
    if n < N:
        if f%3 == 0 and dist[n][f]+X[n] < dist[n][f+1]:
            dist[n][f+1] = dist[n][f]+X[n]
            heappush(que, (dist[n][f+1], encode(n, f+1)))
        if f%3 <= 1 and dist[n][f]+Y[n] < dist[n][f//3*3+2]:
            dist[n][f//3*3+2] = dist[n][f]+Y[n]
            heappush(que, (dist[n][f//3*3+2], encode(n, f//3*3+2)))
        if f//3 == 0 and dist[n][f]+Z[n] < dist[n][f+3]:
            dist[n][f+3] = dist[n][f]+Z[n]
            heappush(que, (dist[n][f+3], encode(n, f+3)))

print(min(dist[N-1]))
0