ID: 1233

Type: Default

2000ms

256MiB

Difficulty: 8

Uploaded By:

Tags>

得物

题目内容

小塔有一个 $n$ 个点 $m$ 条边的无向图，每条边有一个权值 $w_i$ 。

小塔现在计划修人条双向道路，起点是 $1$ 号点，终点是其他顶点。

假设修了这 $k$ 条路后，从 $1$ 号点到其他点的距离为 $d$ ，小塔想知道，可以少修多少条路，使得从 $1$ 号点到其他点的距离仍然为 $d$ 。