lessons/参考实现/05-最短路与类最短路/CodeForces-449B.cpp

#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
struct Edge { int to; long long weight; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k; cin >> n >> m >> k;
    vector<vector<Edge>> g(n);
    vector<tuple<int, int, long long>> roads;
    for (int i = 0; i < m; ++i) {
        int u, v; long long w; cin >> u >> v >> w; --u; --v;
        g[u].push_back({v, w}); g[v].push_back({u, w});
        roads.push_back({u, v, w});
    }
    const long long inf = numeric_limits<long long>::max() / 4;
    vector<long long> train(n, inf), dist(n, inf);
    for (int i = 0; i < k; ++i) {
        int v; long long w; cin >> v >> w; --v;
        train[v] = min(train[v], w);
    }
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    dist[0] = 0; pq.push({0, 0});
    for (int v = 1; v < n; ++v) if (train[v] < inf) {
        dist[v] = train[v]; pq.push({dist[v], v});
    }
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (Edge e : g[u]) if (dist[e.to] > d + e.weight) {
            dist[e.to] = d + e.weight; pq.push({dist[e.to], e.to});
        }
    }
    vector<bool> road_predecessor(n, false);
    for (auto [u, v, w] : roads) {
        if (dist[u] + w == dist[v]) road_predecessor[v] = true;
        if (dist[v] + w == dist[u]) road_predecessor[u] = true;
    }
    int needed = 0;
    for (int v = 1; v < n; ++v) {
        if (train[v] == dist[v] && !road_predecessor[v]) ++needed;
    }
    cout << k - needed << '\n';
}