結果

問題 No.3393 Move on Highway
コンテスト
ユーザー yu23578
提出日時 2025-11-21 23:53:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,644 ms / 3,000 ms
コード長 1,964 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 83,016 KB
実行使用メモリ 164,724 KB
最終ジャッジ日時 2025-11-28 21:00:27
合計ジャッジ時間 51,097 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#チャッピー
import heapq

INF = 10**18

# ステップ1. 入力の受取り
N, M, C = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    w += C  # 利用料金の加算
    G[u].append((v, w))
    G[v].append((u, w))

# ステップ2. 頂点1から頂点iまでの最短距離を求める
Dist_1_to_i = [INF] * N
Q = []  # (距離, 現在の街)
heapq.heappush(Q, (0, 0))
Dist_1_to_i[0] = 0

while Q:
    now_dist, now_pos = heapq.heappop(Q)
    if Dist_1_to_i[now_pos] != now_dist:
        continue
    for nex_pos, nex_dist in G[now_pos]:
        if Dist_1_to_i[nex_pos] > now_dist + nex_dist:
            Dist_1_to_i[nex_pos] = now_dist + nex_dist
            heapq.heappush(Q, (Dist_1_to_i[nex_pos], nex_pos))

# ステップ3. 頂点(状態3,N) から頂点(状態2,i) までの最短距離を求める.
Dist_N_to_i = [[INF] * N for _ in range(4)]
R = []  # (距離, 現在の状態, 現在の街)
heapq.heappush(R, (0, 3, N - 1))
Dist_N_to_i[3][N - 1] = 0

while R:
    now_dist, now_state, now_pos = heapq.heappop(R)

    # 隣接ノード確認
    for nex_pos, nex_dist in G[now_pos]:

        # 状態そのままの遷移
        if Dist_N_to_i[now_state][nex_pos] > Dist_N_to_i[now_state][now_pos] + nex_dist:
            Dist_N_to_i[now_state][nex_pos] = Dist_N_to_i[now_state][now_pos] + nex_dist
            heapq.heappush(R, (Dist_N_to_i[now_state][nex_pos], now_state, nex_pos))

        # 状態3 → 状態2 へ遷移（ガソリン代無料部分）
        if now_state == 3:
            if Dist_N_to_i[2][nex_pos] > Dist_N_to_i[now_state][now_pos] + C:
                Dist_N_to_i[2][nex_pos] = Dist_N_to_i[now_state][now_pos] + C
                heapq.heappush(R, (Dist_N_to_i[2][nex_pos], 2, nex_pos))

# ステップ4. 解答の出力
for i in range(1, N):
    answer = min(Dist_1_to_i[i] + Dist_N_to_i[2][i], Dist_1_to_i[N - 1])
    print(answer)
0