CF - Jzzhu and Cities

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 100;
vector<pair<pair<int64_t,int64_t>,bool>> adj[maxN];
int64_t cost[maxN];
bool used[maxN];

void dijkstra (int n) {
    for (int i = 1; i <= n; ++i) cost[i] = LLONG_MAX;
    cost[1] = 0;
    priority_queue<pair<int64_t,int64_t>> pq;
    pq.push(make_pair(0,1));
    while (!pq.empty()) {
        int64_t node = pq.top().second;
        int64_t node_cost = abs(pq.top().first);
        pq.pop();
        if (cost[node] < node_cost) continue;
        for (pair<pair<int64_t,int64_t>,bool> child : adj[node]) {
            if (cost[child.first.first] >= node_cost + child.first.second) {
                if (cost[child.first.first] == node_cost + child.first.second and used[child.first.first] and !child.second) {
                    cost[child.first.first] = node_cost + child.first.second;
                    used[child.first.first] = false;
                    pq.push(make_pair(-cost[child.first.first],child.first.first));
                } else {
                    if (cost[child.first.first] > node_cost + child.first.second) {
                        used[child.first.first] = child.second;
                        cost[child.first.first] = node_cost + child.first.second;
                        pq.push(make_pair(-cost[child.first.first],child.first.first));
                    }
                }
            }
        }
    }
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         int n,m,k;
         cin >> n >> m >> k;
         for (int i = 1; i <= m; ++i) {
             int64_t u,v,c;
             cin >> u >> v >> c;
             adj[u].push_back(make_pair(make_pair(v,c),false));
             adj[v].push_back(make_pair(make_pair(u,c),false));
         }
         for (int i = 1; i <= k; ++i) {
             int64_t v,c;
             cin >> v >> c;
             adj[1].push_back(make_pair(make_pair(v,c),true));
             adj[v].push_back(make_pair(make_pair(1,c),true));
         }
         dijkstra(n);
         int res = 0;
         for (int i = 1; i <= n; ++i) res += used[i];
         cout << k - res << '\n';
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}