题目内容

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

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

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

dag最短路

前置知识dag最短路 $\\$ 容易想到的思路对原图跑一遍dijstra，单源最短路，求得1到所有点的最短路，然后判断新修的路是不是无用的(也就是dis[pi]<=si)，但是这样显然是不对的。