本题思路:
由题意可知是一道单源最短路问题 那么该如何去解决呢??


先求到每个点的最短路,比较每条高铁和最短路的关系.

倘若高铁比最短路长 显而易见将其拆除
倘若相等 则要判断当前到这个点的最短路是否有两条及以上 若有那么这条铁路也是多余的可以拆除

有了思路以后就要选择用什么办法来实现了
先写了一发SPFA 然后就 TLE了 这可能就是y总说的出题人想卡你的 最坏o(mn)的 恶心题目
那么SPFA不行 便采取堆优化版的dijkstra算法 mlogn 是可以接受的 (就是写起来较为麻烦)

最后再说一句:数据量大 记得开longlong 免得又WA了

题目描述

(中文翻译修改版)
A城有n个城市，m条公路，和k条直接连接首都城市（标号1）和其他城市的高铁。可以看作是一个有边权的无向图。
疫情期间要关闭一部分高铁（没抢到票的就惨喽），该市决定在不改变首都到各城市最短路的前提下停运数量尽可能多的高铁。求最多关闭的高铁数量。
Input
第一行有三个整数n,m,k ( 2 ≤ n ≤ 105 ; 1 ≤ m ≤ 3×105 ; 1 ≤ k ≤ 105 )
接下来m行每行三个整数u,v,x ( 1 ≤ u,v ≤ n ; u!=v; 1 ≤ x ≤ 109 ) 表示一条公路(u,v)长度为x
接下来k行每行两个整数s,y ( 2 ≤ s ≤ n ; 1 ≤ y ≤ 109 )表示一条高铁(1,s)长度为y
可能存在重边
Output
输出一个整数

样例

Input
5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5
Output
2
Input
2 2 3
1 2 2
2 1 3
2 1
2 2
2 3
Output
2

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n, m, k;
int h[N],w[N*20],e[N*20],ne[N*20],idx;//用邻接表来存储图
int num[N];
int x[N],y[N];
long long dist[N];//记得开long long
bool st[N];//用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新
typedef pair<int, int> PII;
int add(int a,int b, int c )//邻接表 熟悉的操作 熟悉的配方
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}


int dijkstra()//套用一波y总的神仙模板
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});//顺序不能换  pair排序时是先根据first，再根据second，这里显然要根据距离排序

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second,distance=t.first;//second指的是哪个点 first是距离

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                num[j]=1;
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
            else if(dist[j]==dist[ver]+w[i])
            {
                 num[j]++;
            }
        }
    }

    int ans=0;
    for(int i=1;i<=k;i++)//参见上面对高铁和最短路之间的关系分类
    {
        if(dist[x[i]]<y[i]) ans++;
        else
        {
            if(dist[x[i]]==y[i]&&num[x[i]]>1)
            {
                num[x[i]]--;
                ans++;
            }
        }
    }
    return ans;
}


int main()
{
    scanf("%d%d%d",&n,&m,&k);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
       scanf("%d%d%d",&a,&b,&c);
       add(a,b,c),add(b,a,c);

    }
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        add(1,x[i],y[i]);
        add(x[i],1,y[i]);
    }
    printf("%d\n",dijkstra());
    return 0;
}