Anti-Dijikstra

元々のグラフを $G$, つばきくんが１辺除いたあとのグラフを $G'$, $G'$上の頂点 $1$ から $k = 1,2,3...$ の最短距離を$P'_1, P'_2, P'_3...$と呼ぶことにします。

(1) すべての頂点 $v$ について $P_v = P'_v$ だったとき

このとき、$G'$ 上に辺がない２頂点に、$P'$ が変化しないような長さの辺を張ればよいです。 ２頂点 $u, v$ に辺を張る際は、長さを$|P_u - P_v|$とすると、条件を満たす中で最短になります。

(2) いくつかの頂点 $v$ について、 $P_v < P'_v$ だったとき

取り除いた辺の2つの端点が $A, B (P_A < P_B)$ であったとします。 頂点の集合 V を、 $P_i < P'_i$ を満たす頂点 $i$ の集合とすると、この中に $B$ が含まれて、 かつ集合内の $B$ 以外のすべての要素 $i$ について $P'_B < P'_i$が成り立ちます。 なぜならば、$P_i < P'_i$であったとき、$G$ 上での $1$から $i$ までの最短経路上につばきくんが取り除いた辺があったはずだからです。 よって、端点のひとつである $B$ が求まりました。

また、 $B$ を端点に持たない辺はどのようにしても条件を満たせないので、答えに $B$ は必ず含まれます。 もう一つの端点 $u$ として考えられるのは、$P_u = P'_u かつP'_B > P'_u$かつ$B$からの辺が存在しない頂点で、 この中で番号が最小のものを選択し、長さは $|P_B - P_u|$ にすればよいです