Edit

【pythonでABC192を解説】E - Train

問題概要

問題ページ

E - Train
E - Train

問題ページへ移動する

問題文

AtCoder国には \(1\) から \(N\) の番号がついた \(N\) 個の都市と、\(1\) から \(M\) の番号がついた \(M\) 本の鉄道があります。

鉄道 \(i\) は都市 \(A_i\) と都市 \(B_i\) の間を結んでおり、時刻が \(K_i\) の倍数になる毎に、双方の都市からそれぞれ他方の都市への列車が発車します。この列車は出発から到着までに \(T_i\) の時間がかかります。

あなたはいま都市 \(X\) にいます。時刻 \(0\) またはそれ以降に都市 \(X\) を発車する列車に乗って移動を開始するとき、都市 \(Y\) には最速でいつたどり着けるか求めてください。都市 \(Y\) にたどり着くことが出来ない場合はそのことを報告してください。
ただし、乗り換えにかかる時間は無視できるため、どの都市においても、あなたの乗っている列車の到着時刻と同時に発車する別の列車に乗り換えることが可能であるとします。

制約

  • \(2 \leq N \leq 10^5\)
  • \(0 \leq M \leq 10^5\)
  • \(1 \leq X,Y \leq N\)
  • \(X \neq Y\)
  • \(1 \leq A_i,B_i \leq N\)
  • \(A_i \neq B_i\)
  • \(1 \leq T_i \leq 10^9\)
  • \(1 \leq K_i \leq 10^9\)
  • 入力は全て整数

問題の考察

ACコード

import sys
import heapq


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m, x, y = list(map(int, input().rstrip('\n').split()))
    edges = [[] for _ in range(n)]
    for i in range(m):
        edge_a, edge_b, cost, time = list(map(int, input().rstrip('\n').split()))
        edges[edge_a-1].append((edge_b-1, cost, time))
        edges[edge_b-1].append((edge_a-1, cost, time))

    ql = [(0, x - 1)]
    heapq.heapify(ql)
    fq = [-1] * n
    while ql:
        cost, now_edge = heapq.heappop(ql)
        if now_edge == y - 1:
            print(cost)
            exit()
        if fq[now_edge] < x - 1:
            fq[now_edge] = x - 1
            for next_edge, p_cost, p_time in edges[now_edge]:
                new_cost = (cost + p_time - 1) // p_time * p_time + p_cost
                heapq.heappush(ql, (new_cost, next_edge))
    print(-1)


if __name__ == '__main__':
    solve()

-Edit
-