得物9.24笔试第3题

求两次单源最短路，注意无向图可能有重边，所以需要去重

#define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define bug(x) cout<<#x<<" is "<<x<<endl
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
vector<int>g[N];
int n, m, k;
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2>& pair) const {
        auto hash1 = std::hash<T1>{}(pair.first);
        auto hash2 = std::hash<T2>{}(pair.second);
        return hash1 ^ hash2;
    }
};
struct node{
    int u;
    ll dis;
    bool operator < (const node & p) const {
        return dis > p.dis;
    }
};
ll d[N];
ll c[N]; 
int vis[N];
unordered_map<pair<int, int>, ll, pair_hash>mp;
void dij(){
    priority_queue<node>q;
    q.push(node{1, 0});
    vis[1] = 1;
    while(!q.empty()){
        node now = q.top();
        q.pop();
        int u = now.u;
        ll dis = now.dis;
        d[u] = dis;
        for(auto v : g[u]){
            if(!vis[v]){
                vis[v] = 1;
                 q.push(node{v, dis + mp[make_pair(u, v)]});  
            }
        }
    }
}
struct node1{
    int u;
    ll z;
}a[N];
void solve(){
    cin >> n >> m >> k;
    
    for(int i = 1; i <= m; i++){
        int x, y;
        ll z;
        cin >> x >> y >> z;
        if (mp.find(make_pair(x, y)) == mp.end()) mp[make_pair(x, y)] = 1e9 + 5;
        if(z < mp[make_pair(x, y)]){
            mp[make_pair(x, y)] = z;
            mp[make_pair(y, x)] = z;
            g[x].push_back(y);
            g[y].push_back(x);
        }
    }
    dij();
    for(int i = 1; i <= n; i++) c[i] = d[i], d[i] = 0, vis[i] = 0;
    for(int i = 1; i <= k; i++){
        cin >> a[i].u >> a[i].z;
        if (mp.find(make_pair(1, a[i].u)) == mp.end()) mp[make_pair(1, a[i].u)] = 1e9 + 5;
        if(a[i].z < mp[make_pair(1, a[i].u)]){
            mp[make_pair(1, a[i].u)] = a[i].z;
            mp[make_pair(a[i].u, 1)] = a[i].z;
            g[1].push_back(a[i].u);
            g[a[i].u].push_back(1);
        }
    }
    dij();
    int ans = 0;
    for(int i = 1; i <= k; i++){
        if(a[i].z > d[a[i].u]) ans++;
        else if(a[i].z == d[a[i].u]) {
            if(a[i].z >= c[a[i].u]) ans++;
        }
    }
    cout << ans << endl;
}
int main(){
    IO;
    solve();
}
/*
2 2 2
1 2 2
2 1 3
2 2
2 3

*/