色と経路

経路 $P$ で色 $c$ 以外の辺を通る回数を $f(P,c)$ とする。費用は $\min_c f(P,c)$ なので、答えは $\min_P\min_c f(P,c)=\min_c\min_P f(P,c)$。色 $c$ を固定し、その色の辺の重みを 0、他を 1 として 0-1 BFS で最短距離を求める。全色の結果の最小値が答えである。 重み 0 の緩和はデックの前、重み 1 は後ろへ挿入する。挿入時の距離を保存し、古い項目を飛ばす。時間 $O(K(V+E))$、空間 $O(V+E)$。重みが非負なので閉路を除去しても固定色の費用は増えない。サブタスク 1 は DFS ですべての単純経路を列挙して色数を数えればよい。緩い上限は $O(E!K)$ で、$E\leq8$ なら十分。答えと有限最短距離は 0 以上 $V-1$ 以下で、64ビット整数に収まる。

Solution written by GPT6.1