技術室奥プログラミングコンテスト#4 Day1：H - don't be late

問題
解法
解答

問題

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_h

解法

各駅での乗り換え時間は，その駅につく路線の所要時間に加算してしまってよい．こうすることで，辺だけにコストを乗せることができたのでダイクストラ法を適用できる．ダイクストラ法の中で今いる頂点と時刻の情報を持っているので，各辺で移動するまでに待たなければいけない時間も計算できる．これで頂点 K までの所要時間が求まる．O(MlogN)．