ABC035 D - トレジャーハント

問題：https://atcoder.jp/contests/abc035/tasks/abc035_d

解答：Submission #11481223 - AtCoder Beginner Contest 035

解法：待つのは1種類の頂点でよい。なのでa[i] * (t - d[0, i] - d[i, 0])を全てのiで試せばよい。

d[0, i]はダイクストラで間に合うが、d[i, 0]を全てのiで行うのは普通にやってはできない。

ここで全ての辺を逆向きにし、そのグラフでd'[0, i]を計算することでd[i, 0]を求めることができる。