#P18926. [2026多校联测]公交
[2026多校联测]公交
公交
题目描述
有 座城市,彼此间通过 条道路连接且 座城市互相连通。第 座城市有 个人。假设首都是 ,现在你要修建 条到 的公交线路。若你选择修建线路 ,则 到 上的所有点都将被包括在公交线路中。对于不在公交线路上的点,居民需要沿最短路径走到一条最近的被包括在公交线路的点上,所产生的不满度为此距离乘上该点的人数。
你需要合理规划这 条线路,使得不满度之和最小。同时,你需要求出首都为 的所有情况的答案。
输入格式
第一行两个整数 。
第二行 个整数表示 。
接下来的 行每行两个整数 ,表示一条边。
输出格式
一行 个整数,表示首都为 时的答案。
样例输入
5 2
82822 92268 1983 93812 57626
1 2
2 3
2 4
4 5
样例输出
0 1983 0 1983 0
数据范围与约定
对于所有数据,,。
| 数据点 | ||
|---|---|---|