本問題で与えられるグラフは、辺 \((a_i, b_i)\) の重みを \(\max(a_i, b_i)\) で定めるものとすると \((\max, \min)\) 半環上の全点対最短距離問題になります。

\((\max, \min)\) 半環においては、一般の全点対最短距離と異なる特徴が一つあります。 それは、辺重みの小さい順に辺を貼った時、既存の最短距離が更新されることは無いということです。 この事実を利用し、 \(O(\frac{N^3}{\rm wordsize})\) 時間アルゴリズムを開発することができます。

辺を新たに追加する関数 \({\rm addEdge}(s, t, w)\) を設計します。 この関数は頂点 \(s\) から頂点 \(t\) に重み \(w\) の辺を貼るものとします。

この関数の処理を確認します。

まず、 \(s\) から \(t\) に重み \(w\) の辺を追加します。 次に、この辺が追加されたことで最短距離の更新が起こった場合、その更新処理を行わないといけません。 このような更新処理が発生する場合はFloyd-Warshall法を考えると次の二通りに限られます。

• ある頂点 \(a\) が存在して、辺 \((a, s)\) が存在するが辺 \((a, t)\) が存在しない場合、 \(a\) から \(t\) の最短距離を \(\infty\) から \(w\) に更新する
• ある頂点 \(b\) が存在して、 辺 \((t, b)\) が存在するが辺 \((s, b)\) が存在しない場合、 \(s\) から \(b\) の最短距離を \(\infty\) から \(w\) に更新する

この二つの処理は、 \({\rm addEdge}(a, t, w)\) を呼ぶという処理と \({\rm addEdge}(s, b, w)\) を呼ぶという処理と考えることができます。 従って、 \(a\) と \(b\) の候補を償却 \(O(\frac{N}{\rm wordsize})\) で列挙できれば、辺の本数は \(O(N^2)\) であることから全体の計算量を \(O(\frac{N^3}{\rm wordsize})\) で抑えることができます。

さて、 \(a\) を列挙する処理は逆辺上で \(b\) を列挙する処理と同一なので、 \(b\) を列挙する処理を述べることとします。 \(G[v]\) を頂点 \(v\) から直接辿り着ける頂点の集合とすると、 \(b\) は \(\overline{G[s]} \cup G[t]\) の元として表せます。 これは、 \(G[v]\) をBitSetとして表していると \(O(\frac{N}{\rm wordsize})\) で求めることができます。

実装は以下のようになります。 ACコード

 /**
 * (max, min)半環上の全点対最短距離を計算します。
 * @param [n] 頂点数
 * @param [edges] 辺、より後ろに格納された辺の方が重みが大きいものとする
 * @return 全点対最短距離を保存したグラフ
 */
fun <T> allShortestDistance(n: Int, edges: Array<Edge<T>>): Graph<T> {
	val graph = Graph<T>(n)
	val forward = Array(graph.n) { BitSet(graph.n) } // グラフの隣接行列
	val back = Array(graph.n) { BitSet(graph.n) } // 逆グラフの隣接行列
	val queue : Queue<Edge<T>> = ArrayDeque()
	for (e in edges) { // 重みの小さい順に辺を追加していく
		queue += e
		while(!queue.isEmpty()) { // 追加した辺によって新たに辿り着けるようになった頂点対の辺も追加する
			val (s, t, w) = queue.peek()
			graph[s][t] = queue.poll()
			forward[s][t] = true
			back[t][s] = true
			val next = forward[t].clone() as BitSet // s -> t -> uとなるs -> uに対してパスを追加
			next.andNot(forward[s]) // uは、tから行けるがsから行けない頂点
			forward[s].or(next)
			val last = back[s].clone() as BitSet // r -> s -> tとなるr -> sに対してパスを追加
			last.andNot(back[t]) // rは、sの逆辺から行けるがtの逆辺から行けない頂点
			back[t].or(last)
			loopBitSet(next) {queue += Edge(s, it, w)}
			loopBitSet(last) {queue += Edge(it, t, w)}
		}
	}
	return graph
}