ABC192 E - Train

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import datetime

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def it(): return tuple(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def dijkstra(N, start, graph):
    dist = [INF] * N  # 各頂点までの距離を保持する配列
    dist[start] = 0  # 開始始点の頂点は距離をゼロとする
    visited = [0] * N  # 各頂点の訪問状態を保持する配列[0: 未訪問, 1: 訪問済み]
    heap = [(0, start)]  # 距離と始点頂点（自分自身への移動距離はゼロ）
    heapq.heapify(heap)  # 距離と頂点の情報を距離で優先度付きキューとする
    while heap:
        # 頂点uとuに到達するまでの距離
        min_cost, u = heapq.heappop(heap)

        # さらに小さい距離で既に到達済みの場合はcontinue
        if dist[u] < min_cost:
            continue
        visited[u] = 1  # 頂点uを訪問済みにする

        # グラフの情報から接する頂点と移動距離を順に処理
        for cost, k, v in graph[u]:
            if visited[v] != 1:
                # 移動時のコスト計算で
                # 移動可能な時間まで待機するようにする
                q = math.ceil(dist[u]/k) * k + cost
                if q < dist[v]:
                    # 未到達かつ小さい距離で移動できる場合には
                    # 距離の更新と優先度付きキューに(距離, 頂点)の情報を追加
                    dist[v] = q
                    heapq.heappush(heap, (dist[v], v))
    return dist


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M, X, Y = il()
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b, t, k = il()
        graph[a-1].append((t, k, b-1))
        graph[b-1].append((t, k, a-1))

    dist = dijkstra(N, X-1, graph)
    print(-1 if dist[Y-1] == INF else dist[Y-1])


if __name__ == '__main__':
    main()

考え方

各都市を頂点、電車を辺としてグラフに置き換えます。
あとは頂点Xから頂点Yまでの最短距離を求める問題です。
ダイクストラ法を用いるとグラフの最短距離を求めることが出来ます。

ただし、注意点として、時刻がKの倍数のときだけ電車に乗ることが出来ます。
したがって、頂点から異なる頂点に移動するときのコストの計算に現在時刻からKの倍数になるまでの待機時間の考慮が必要となります。