Open nagato1208 opened 5 years ago
https://nagato1208.github.io/2019/09/06/codeforces-1076D-Edge-Deletion/#more
描述给定一个n个点，m条边, 用邻接表表示的无向连通图. 每个点i都和点1有一个最短距离. 现在需要删去一些边，让剩余的边数最多为k，并且让尽量多的到节点1的最短距离保持不变. 给定的边编号1~m，找到最佳删边方案，打印保留的边的编号. 思路dijkstra长时间不写还给WA了几发… 直接从起点1开始遍历最短路, 把找到的前min(n-1, k)条unique的边加入结果. 代码123456789
https://nagato1208.github.io/2019/09/06/codeforces-1076D-Edge-Deletion/#more
描述给定一个n个点，m条边, 用邻接表表示的无向连通图. 每个点i都和点1有一个最短距离. 现在需要删去一些边，让剩余的边数最多为k，并且让尽量多的到节点1的最短距离保持不变. 给定的边编号1~m，找到最佳删边方案，打印保留的边的编号. 思路dijkstra长时间不写还给WA了几发… 直接从起点1开始遍历最短路, 把找到的前min(n-1, k)条unique的边加入结果. 代码123456789