题意翻译

给你个点，条带权边的无向图，以及条特殊边，每条边连接和 。

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

输入格式

第一行3个数字

下面行，每行3个数字

再下面 行，每行两个数字，代表连接到 的边，权值为

输出格式

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

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

数据范围和约定

对于的数据，保证

分析

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

这里只说真做法。

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

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

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