题意翻译

给你$n$个点，$m$条带权边的无向图，以及$k$条特殊边，每条边连接$1$和$k_i$ 。

问在保证每个点到$1$的最短距离不变的情况下，最多可以删除这$k$条边中的多少条边，

输入格式

第一行3个数字$n,m,k$

下面$m$行，每行3个数字$u_i,v_i,x_i$

再下面$k$ 行，每行两个数字$k_i,v_i$，代表连接$1$到$k_i$ 的边，权值为$v_i$

输出格式

输出仅有一行，为一个整数$ans$。表示能删除的最大边数。

Input & Output ‘s examples

Input ‘s eg 1

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 ‘s eg 1

2

Input ‘s eg 2

2 2 3
1 2 2
2 1 3
2 1
2 2
2 3

Output ‘s eg 2

2

数据范围和约定

对于$100\%$的数据，保证$1 < u_i , v_i , s_i < n < 10^5$

$1 < k < 10^5$

$1 < m < 3 \times 10^5$

$1 < x_i , y_i < 10^9$

分析

听说这题假做法很多？？？

这里只说真做法。

对于每一条特殊的边，它能被删除，当且仅当它不在从$1$到任意一点的唯一最短路中。

因此，我们模拟$Dijkstra$的过程，判断每一条特殊边是否在最短路中即可。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 400001

using namespace std;

int n , m , k;

struct Edge{
    int to;
    int last;
    ll dis;
}edge[N << 1];

int edge_num;
int head[N << 1];
bool vis[N << 1];

I void add_edge(int from , int to , ll dis){
    edge[++ edge_num] = (Edge){to , head[from] , dis};
    head[from] = edge_num;
}

#define pairs pair<ll , ll > 

priority_queue<pairs >  Q;

int main(){
    ll u , v , w;
    scanf("%d %d %d" , &n , &m , &k);
    for(int i = 1; i <= m; i ++){
        scanf("%lld %lld %lld" , &u , &v , &w);
        u --;
        v --;
        add_edge(u , v , w);
        add_edge(v , u , w);
    }
    for(int i = 1; i <= k; i ++){
        scanf("%lld %lld" , &v , &w);
        v --;
        Q.push(make_pair(- w  , v - n));
    }
    Q.push(make_pair(0 , 0));
    ll ans = 0;
    while(!Q.empty()){
        pairs v = Q.top();
        Q.pop();
        if(v.second < 0){
            v.second += n;
            if(vis[v.second]){
                ans ++;
            }
        }
        if(vis[v.second]){
            continue;
        }
        vis[v.second] = true;
        for(int i = head[v.second] ; i ; i = edge[i].last){
            Q.push(make_pair(v.first - edge[i].dis , edge[i].to));
        }
    }
    printf("%lld\n" , ans);

    return 0;
}

THE END