색깔과 경로

경로 $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을 주면 $\min_P f(P,c)$는 최단 거리이다. 각 색에 대해 0-1 BFS를 수행하고 최솟값을 취한다. 0-1 BFS에서 가중치 0 완화는 덱 앞, 가중치 1 완화는 덱 뒤에 넣는다. 갱신 당시 거리도 함께 저장하고 오래된 항목은 건너뛴다. 시간 $O(K(V+E))$, 공간 $O(V+E)$이다. 음수가 없는 가중치이므로 최단 경로에서 사이클을 제거해도 값이 증가하지 않는다. 서브태스크 1은 모든 단순 경로를 DFS로 열거하고 각 색 개수를 센다. $E\leq8$에서 탐색 크기는 충분히 작으며 느슨한 상한은 $O(E!K)$이다. 정답은 $0$ 이상 $V-1$ 이하이고 거리 배열의 유한 값도 최대 $V-1$이므로 64비트 정수 범위를 넘지 않는다.

Solution written by GPT6.1