JOI2019/2020 本選問題4 オリンピックバス (Olympic Bus) をΟ((M+N)logM+N^3)で解く

公式解説が出るまでの気休め

問題概要

$N$ 頂点 $M$ 辺からなる有向グラフが与えられる。頂点には $1$ から $N$ までの番号がついている。 $i$ 番目の辺は頂点 $u_i$ から $v_i$ への辺で、長さは $c_i$ 、重みは $d_i$ である。次の操作を高々 $1$ 回だけ行える。

整数 $i$ を $1$ つ選んで、 $i$ 番目の辺の向きを逆にする。コストを $d_i$ 払う。

操作の後、次で定義されるコストを払う。

頂点 $1$ から頂点 $N$ までの最短距離と、頂点 $N$ から頂点 $1$ までの最短距離の和
ただし、経路がない時のコストは $\infty$ である。

払うコストの最小値を求めよ。

制約

$2 \le N \le 200$
$1 \le M \le 50000$
$0 \le c_i \le 10^6$
$0 \le d_i \le 10^9$

解法

どの辺も逆にしないときのコストは普通に求まる。

辺 $i$ を逆にしたときのコストを、すべての $i$ について求めればよい。

辺 $i$ を逆にしたときの $1$ → $N$ の距離と $N$ → $1$ の距離を、別々に求めることにする。 $1$ → $N$ が求まるなら、同じようなことを $N$ → $1$ に対して行えばよいから、前者の場合だけを考える。

どの辺も逆にしないときの $1$ → $N$ の距離 $D$ を求めておく。辺 $i$ を逆にしたときの $1$ → $N$ の距離 $D_i$ は、 $D$ より小さくなるか、 $D$ より大きくなるか、 $D$ と等しい、のいずれかを満たす。

距離 $D_i$ が $D$ より小さくなる場合の検出

辺 $i$ を逆にして新たに発生する経路の中で最短なものは、 $1$ → $v_i$ の最短経路、 $v_i$ → $u_i$ の辺 $i$ 、 $u_i$ → $N$ の最短経路を順につなげたものである。この経路の距離 $D_{new}$ を求めたい。

辺 $i$ を消したときの $1$ → $v_i$ の距離 $D_{1v_i}$ と $u_i$ → $N$ の距離 $D_{u_iN}$ が求まっていれば、 $D_{new} = D_{1v_i}+c_i+D_{u_iN}$ と求めることができる。この $D_{new}$ が $D$ より小さいときのみ、最短距離が小さくなって、 $D_i = D_{new}$ となる。

辺 $i$ を消したときの $D_{1v_i}$ と $D_{u_iN}$ を求めなければならないが、これはもとのグラフで頂点 $1$ および頂点 $N$ からダイクストラをすることで、すべての $i$ について $D_{1v_i}^*$ および $D_{u_iN}^*$ をまとめて求めることができる。

こうやって求めた $D_{1v_i}^*$ , $D_{u_iN}^*$ , $D_{new}^*$ には、辺 $i$ (向きを逆にしていないもの)を経路に使ってしまっている場合があるが、この場合は $D_{new}^* \geq D$ となり、影響がない。なぜなら、例えば $D_{1v_i}^*$ の計算で辺 $i$ を使ってしまった場合、 $D_{1v_i}^*=D_{1u_i}+c_i$ であり、 $D_{1u_i}+D_{u_iN} \geq D$ であるから、

$D_{new}^* = D_{1v_i}^*+D_{u_iN}+c_i = D_{1u_i}+D_{u_iN}+2*c_i \geq D$

となる。したがって、 $D_i$ の計算には影響を与えないことがわかる。

辺 $i$ を使わない条件のもとでの $1$ → $v_i$ の距離を $D_{1v_i}$ とすると、 $D_{1v_i} \geq D_{1v_i}^*$ であり、辺 $i$ (向きを逆にしていないもの)を使わない本来求めるべき $D_{new}$ について、 $D_{new} \geq D_{new}^*$ である。つまり、辺 $i$ (向きを逆にしていないもの)を使ってしまったときは、 $D_{new}$ が $D$ より小さくならないために、距離が小さくなる検出をする必要がなく、また異常な値によって $D_i$ を更新することもない。

距離 $D_i$ が $D$ より大きくなる場合の検出

どの辺も逆にしないときの $1$ → $N$ の最短経路 $Path$ を1つ選ぶ。

$Path$ に含まれていない辺の向きを逆にしても、距離 $D$ の経路 $Path$ が残っているのだから、 $1$ → $N$ の距離は $D$ より大きくならない。したがって、 $Path$ に含まれる辺についてのみ、新しい最短距離を計算すればよい。

$Path$ に含まれる辺 $i$ を逆にした場合について考える。辺 $i$ を逆にすると、 $Path$ は $2$ つに分断されて、パス $Q = (1 \rightarrow \ldots \rightarrow u_i)$ とパス $R = (v_i \rightarrow \ldots \rightarrow N)$ に分かれる。パス $Q$ に含まれる頂点集合を $U$ 、パス $R$ に含まれる頂点集合を $V$ とおく。パス $Q$ は $1$ → ( $U$ 内の頂点) の最短経路を含んでいて、パス $R$ は ( $V$ 内の頂点) → $N$ の最短経路を含んでいることがわかる。(そうでないと、 $Path$ が最短経路でなくなる)

新しい $1$ → $N$ の最短経路は、 $Q$ の一部を通った後、 $Path$ に含まれない辺をいくつか経由して、 $R$ の一部を通るような経路であることを示せる。 $1$ → $N$ のどの経路 $X$ についても、最後に訪れた $U$ 内の頂点 $x$ と、 $x$ よりも後に訪れた頂点の中で、最初に訪れた $V$ 内の頂点 $y$ がある。パス $Q$ には $1$ → $x$ の最短経路が、パス $R$ には $y$ → $N$ の最短経路が含まれているのだから、 $Q$ の一部を通って頂点 $x$ に移動し、 $Path$ に含まれない辺を $X$ の通りにいくつか経由して頂点 $y$ に移動し、 $R$ の一部を通って頂点 $N$ に移動するような経路を考えると、この経路の距離はパス $X$ の距離以下であるからだ。

$Q$ の一部を通るときに最後に訪れる頂点 $x \in U$ と、 $R$ の一部を通るときに最初に訪れる頂点 $y \in V$ を固定する。 $1$ → $x$ の距離 $D_{1x}$ と、 $y$ → $N$ の距離 $D_{yN}$ は、事前に計算しておける。 $Path$ に含まれない辺をいくつか経由して頂点 $x$ から頂点 $y$ に移動する部分の最短距離を $D_{xy}$ とすると、新しい最短距離は、 $\min_{(x,y)} \{ D_{1x}+D_{xy}+D_{yN} \}$ である。 $D_{xy}$ は、以下のようにして求めることができる。

元のグラフから $Path$ に含まれる辺をすべて取り除く。このグラフにおいて、ワーシャルフロイドを用いれば、すべての $(x,y)$ の組について、最短距離 $D_{xy}$ をまとめて計算できる。また、この結果は $Path$ 内のどの辺 $i$ についても使いまわすことができる。つまり、ワーシャルフロイドを行う回数は $1$ 回だけでよい。