WUPC2012 E. 会場への道

問題

N個の街をつなぐM個の道の情報が与えれる。道の情報として、移動元の街、移動先の街、かかる時間が与えられる。街番号0から街番号N-1まで最短時間で移動したい。ただし、ゴールするときの時間は4か7で割り切れるようにしたい。
最短の到達時間を返す。

考え方

「位置と時間」を状態にダイクストラ。

ただし、枝狩りとして、その街に来た時の時間を保持して、すでにその時間でその街に来ていれば探索しない。が、そのまま時間を保持しようとするといくらでも大きくなってしまう。

ある街aに、すでに時刻uで来ていた場合、新たに時刻tで来たときに探索を続けるべきかどうかを考える。
最終的に4か7で割り切れるかどうか考えたいので、時刻tと時刻uについて周期性から4*7=28で割った余りを考えればよい。