容易想到最短路 DAG 求出来，起初我以为要求最小割，但这是错误的，因为可能有多条边联通了一个点的情况，这时候选择最小割不一定是最优的
我们猜想一个思路：答案一定是包含 \(1\) 号节点的连通块全部填 \(N\) ，剩下的填 \(S\) 。发现在最短路 DAG 中， \(1 \rightarrow n\) 的所有路径里经过超过 \(2\) 条边的所有路径都可以被覆盖。而比较特殊的就是 \(1 \rightarrow n\) 直接有边，这种情况只需保证 \(1\) 和 \(n\) 颜色相同即可
注意没有答案当且仅当 \(n = 2,k = 1\)
最终复杂度 \(O((n+m) \log (n+m))\) ，复杂度瓶颈在于 dijkstra
- 2021 Programming Collegiate ACM-ICPC Contest2021 programming collegiate acm-icpc 2022 programming collegiate acm-icpc subregional programming acm-icpc contest programming collegiate provincial contest programming collegiate jiangsu contest international programming collegiate contest programming collegiate mianyang contest programming collegiate contest guilin programming collegiate shenzhen contest programming collegiate shanghai contest