20231023: NOIP2023-div2模拟赛24
A. 公园
题意
给一个无向图\(G=(V,E)\), 求一个\(X\), 使得\(D\times X+\sum\limits_{e\in G,dist(1,e.u)> X or dist(1,e.v)> X}cost(e)\)最小, 求最小值
赛时思路
非常的简单啊
算法概述
处理出一号点到所有点的最短路, 按最短路从大到小排序依次加入集合, 加入集合的时候把对应的连边也加入,
给一个无向图\(G=(V,E)\), 求一个\(X\), 使得\(D\times X+\sum\limits_{e\in G,dist(1,e.u)> X or dist(1,e.v)> X}cost(e)\)最小, 求最小值
非常的简单啊
处理出一号点到所有点的最短路, 按最短路从大到小排序依次加入集合, 加入集合的时候把对应的连边也加入,