题解 | #小红修道路#

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

template <typename T>
auto dijkstra(const vector<vector<pair<int, int>>> &g,
              const vector<T> &w, int start) -> pair<vector<int64_t>, vector<int>> {
    vector<int64_t> dis(g.size(), -1);
    vector<int> cnt(g.size()); 
    cnt[start] = 1;

    priority_queue<tuple<int64_t, int, int>> q;
    q.emplace(0, start, -1);
    while (!q.empty()) {
        auto [d, u, f] = q.top();
        q.pop();

        if (f != -1 && (dis[u] == -1 || dis[u] == -d)) {
            cnt[u]++;
        }
        if (dis[u] != -1) continue;
        dis[u] = -d;

        for (auto [v, j] : g[u]) {
            q.emplace(d - w[j], v, u);
        }
    }
    return {dis, cnt};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<pair<int, int>>> g(n);
    vector<int> w(m + k);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v >> w[i];
        u--, v--;
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }

    vector<pair<int, int>> p;
    for (int i = m; i < m + k; i++) {
        int s;
        cin >> s >> w[i];
        s--;
        p.emplace_back(s, w[i]);
        g[0].emplace_back(s, i);
        g[s].emplace_back(0, i);
    }

    auto [dis, cnt] = dijkstra(g, w, 0);

    int ans = 0;
    for (auto [s, y] : p) {
        if (dis[s] < y) {
            ans++;
        } else if (cnt[s] >= 2) {
            ans++;
            cnt[s]--;
        }
    }

    cout << ans << "\n";

    return 0;
}

import java.util.*;

public class Main {
    static class Edge {
        int v, idx;
        Edge(int v, int idx) {
            this.v = v;
            this.idx = idx;
        }
    }
    
    static class State {
        long dist;
        int u, from;
        State(long dist, int u, int from) {
            this.dist = dist;
            this.u = u;
            this.from = from;
        }
    }
    
    static Pair<long[], int[]> dijkstra(List<List<Edge>> g, int[] w, int start) {
        int n = g.size();
        long[] dist = new long[n];
        Arrays.fill(dist, -1);
        int[] cnt = new int[n];
        cnt[start] = 1;
        
        PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> Long.compare(a.dist, b.dist));
        pq.offer(new State(0, start, -1));
        
        while(!pq.isEmpty()) {
            State cur = pq.poll();
            
            if(cur.from != -1 && (dist[cur.u] == -1 || dist[cur.u] == cur.dist)) {
                cnt[cur.u]++;
            }
            if(dist[cur.u] != -1) continue;
            dist[cur.u] = cur.dist;
            
            for(Edge e : g.get(cur.u)) {
                pq.offer(new State(cur.dist + w[e.idx], e.v, cur.u));
            }
        }
        
        return new Pair<>(dist, cnt);
    }
    
    static class Pair<T, U> {
        T first;
        U second;
        Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        
        List<List<Edge>> g = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        
        int[] w = new int[m + k];
        for(int i = 0; i < m; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            w[i] = sc.nextInt();
            g.get(u).add(new Edge(v, i));
            g.get(v).add(new Edge(u, i));
        }
        
        List<Pair<Integer, Integer>> p = new ArrayList<>();
        for(int i = m; i < m + k; i++) {
            int s = sc.nextInt() - 1;
            w[i] = sc.nextInt();
            p.add(new Pair<>(s, w[i]));
            g.get(0).add(new Edge(s, i));
            g.get(s).add(new Edge(0, i));
        }
        
        Pair<long[], int[]> result = dijkstra(g, w, 0);
        long[] dist = result.first;
        int[] cnt = result.second;
        
        int ans = 0;
        for(Pair<Integer, Integer> edge : p) {
            if(dist[edge.first] < edge.second) {
                ans++;
            } else if(cnt[edge.first] >= 2) {
                ans++;
                cnt[edge.first]--;
            }
        }
        
        System.out.println(ans);
    }
}

from heapq import heappush, heappop
from typing import List, Tuple
import sys
input=sys.stdin.readline

def dijkstra(g: List[List[Tuple[int, int]]], w: List[int], start: int) -> Tuple[List[int], List[int]]:
    n = len(g)
    dis = [-1] * n
    cnt = [0] * n
    cnt[start] = 1
    
    q = []  # 使用负数实现最大堆
    heappush(q, (0, -start, 1))  # (distance, vertex, from)
    
    while q:
        d, u, f = heappop(q)
        d=-d
        u=-u
        f=-f
        if f != -1 and (dis[u] == -1 or dis[u] == -d):
            cnt[u] += 1
        if dis[u] != -1:
            continue
        dis[u] = -d
        
        for v, j in g[u]:
            heappush(q, (-d + w[j], -v, -u))
    
    return dis, cnt

n, m, k = map(int, input().split())
g = [[] for _ in range(n)]
w = [0] * (m + k)

# 读入原图的边
for i in range(m):
    u, v, weight = map(int, input().split())
    u -= 1
    v -= 1
    w[i] = weight
    g[u].append((v, i))
    g[v].append((u, i))

# 读入计划修的路
p = []
for i in range(m, m + k):
    s, length = map(int, input().split())
    s -= 1
    w[i] = length
    p.append((s, length))
    g[0].append((s, i))
    g[s].append((0, i))

dis, cnt = dijkstra(g, w, 0)

ans = 0
for s, y in p:
    if dis[s] < y:
        ans += 1
    elif cnt[s] >= 2:
        ans += 1
        cnt[s] -= 1

print(ans)