https://ac.nowcoder.com/acm/contest/1104/B 注意到\(\text{K}\)只有\(12\),因此对起点与每个毕经边对应的点单源最短路,\(\text{DP}\)出最优解 #include <cstring> #include <cstdio> #include <...
题面 n <= 50000,m <= 200000,k <= 12 题解 可以从K条边的两端和1结点出发各进行一次O(nlogn)的Dijk,然后就浓缩成了一个最多只有25个点的小完全图,然后就像旅行商问题一样,用状态压缩DP做。 代码 ...