kaage精進録

雑な解説とかライブラリとかおきもちの垂れ流しです。

2013JOI春合宿1-1 Bus Tour

だるかったので高速化したら通った

問題リンク

解法

とりあえず交点を求めてダイクストラしたいおきもちになるが、めんどくさいので愚直なダイクストラを書いてみる。

路線と場所ごとに距離を持たなければいけないが、これは unordered_map を使うのが最適(だと思う。)

これでもTLEするので、2番目までの最短時間を持って、それを超えたところで枝刈りすると通るようになる。

提出コード