特殊な遷移の最短経路問題に帰着することができます。

初期状態で頂点 \(a\) から頂点 \(b\) へ向かう辺を使うときのコストは

• \(a-b\) 間の辺の色を変える
• \(a-b\) 間の辺の色と同色な \(a\) に接続する他の辺の色を変える。

のいずれかになります。

さらに、「\(a-b\) 間の辺の色を変える」で遷移して、次に \(b\) から\(c\) へ遷移する場合を考えます。

\(a-b\) と \(b-c\) の色が異なるならば初期状態と同様です。

\(a-b\) と \(b-c\) が同色の場合は、「\(b-c\) 間の辺の色と同色な \(b\) に接続する他の辺の色を変える」操作については辺 \(b-a\) の色を書き換え済みなのでその分のコストを削減できます。

この性質を利用して、

\[ dp1[i] := 最後に書き換えた辺を考慮しない頂点 1 から 頂点 i までのコスト\\ dp2[i][c] := 最後に色 c の頂点を書き換えて頂点 1 から 頂点 i まで遷移したときのコスト \]

という状態と組み合わせてダイクストラ法を実装することができます。

解答例(C#): https://atcoder.jp/contests/joi2021ho/submissions/23635585