前置知识dag最短路 容易想到的思路对原图跑一遍dijstra,单源最短路,求得1到所有点的最短路,然后判断新修的路是不是无用的(也就是dis[pi]<=si),但是这样显然是不对的。
3 2 2
1 2 2
2 3 3
2 1
3 4
小红有一个n个点 m 条边的无向图,每条边有一个权值 wi。
小红现在计划修人条双向道路,起点是1号点,终点是其他顶点。
假设修了这k条路后,从1号点到其他点的距离为d,小红想知道,可以少修多少条路,使得从 1 号点到其他点的距离仍然为 d。
第一行三个整数 n,m,k,表示点数,边数,以及小红计划修的路数。
接下来 m 行,每行三个整数ui,vi,wi,表示一条边的两个端点以及权值。
接下来k行,每行两个整数pi,si,表示计划修从1号点到pi号点的一条路,长度为 si。
1≤n,m,k≤105
1≤ui,vi,pi≤105
1≤wi,si≤109
输出一个整数,表示可以少修的路数。
输入
2 2 2
1 2 2
2 1 3
2 2
2 3
输出
2
说明
从1号点到2号点的距离为2,修路不能改变最短距离,两条路都可以不修。