题目内容

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

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

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

dag最短路

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

3 2 2
1 2 2
2 3 3
2 1
3 4