发布于2021-11-23
AcWing第2场周赛 — C.边的删减
给定一个由 n 个点和 m 条边组成的无向连通加权图。 设点 1 到点 i 的最短路径长度为 di。 现在，你需要删掉图中的一些边，使得图中最多保留 k 条边。 如果在删边操作全部完成后，点 1 到点 i 的最短路径长度仍为 di，则称点 i 是一个优秀点。 你的目标是通过合理进行删边操作，使得优秀点的数量尽可能大。
标签：最短路径