小红修道路

[题目链接](https://www.nowcoder.com/practice/b22011bdda6f43ddb9a34933ea5d737f)

思路

有一个 个点 条边的无向图，小红计划修 条从 1 号点出发的道路。每条计划道路指定了终点 和长度 。问：最多能少修多少条路，使得从 1 号点到其他所有点的最短距离不变？

关键观察

把所有计划修的道路也当做边加到图里，跑一遍 Dijkstra，得到每个点的最短距离 。

对于一条计划道路 ：

  • 如果 ，它根本不在任何最短路上，一定可以省掉。
  • 如果 ，它可能是到达 的最短路径之一。但如果存在其他方式也能用 的代价到达 ，那这条路也可以省掉。

哪些节点"真的需要"一条计划道路？

如果某个节点 可以通过原始图中的边从其他已经"覆盖"的节点到达（即存在原始边 使得 且 已被覆盖），那它不需要计划道路。

按 从小到大处理每个节点。节点 1 天然被覆盖。对于每个后续节点 ：

  1. 遍历 的所有原始边 ，如果存在某个已覆盖的 满足 ，那 也被覆盖，不需要计划道路。
  2. 否则， 必须靠一条计划道路来到达——我们保留一条最优的即可。

最终答案

设有 个节点需要计划道路，每个节点只需保留 1 条。答案就是 。

为什么按距离排序是正确的？

Dijkstra 的松弛顺序保证了：当我们处理到节点 时，所有 更小的节点已经被处理完毕。如果 能通过原始边从更近的节点到达，那些节点的"覆盖"状态已经确定了，不会漏判。

复杂度

  • 时间复杂度：，Dijkstra 的复杂度，加上排序和遍历边。
  • 空间复杂度：

代码

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

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

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<pair<int,long long>>> orig(n + 1);
    for(int i = 0; i < m; i++){
        int u, v;
        long long w;
        cin >> u >> v >> w;
        orig[u].push_back({v, w});
        orig[v].push_back({u, w});
    }

    vector<long long> bestPlan(n + 1, LLONG_MAX);
    vector<pair<int,long long>> planned(k);
    for(int i = 0; i < k; i++){
        cin >> planned[i].first >> planned[i].second;
        bestPlan[planned[i].first] = min(bestPlan[planned[i].first], planned[i].second);
    }

    // 建包含最优计划道路的完整图
    vector<vector<pair<int,long long>>> adj(n + 1);
    for(int u = 1; u <= n; u++) adj[u] = orig[u];
    for(int v = 2; v <= n; v++){
        if(bestPlan[v] != LLONG_MAX){
            adj[1].push_back({v, bestPlan[v]});
            adj[v].push_back({1, bestPlan[v]});
        }
    }

    // Dijkstra
    const long long INF = 1e18;
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    pq.push({0, 1});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        for(auto &[v, w] : adj[u]){
            if(dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    // 按 dist 排序，贪心判断哪些节点需要计划道路
    vector<int> order;
    for(int v = 1; v <= n; v++)
        if(dist[v] < INF) order.push_back(v);
    sort(order.begin(), order.end(), [&](int a, int b){
        return dist[a] < dist[b];
    });

    vector<bool> covered(n + 1, false);
    covered[1] = true;
    int need = 0;

    for(int v : order){
        if(v == 1) continue;
        bool ok = false;
        for(auto &[u, w] : orig[v])
            if(covered[u] && dist[u] + w == dist[v]){ ok = true; break; }
        if(ok){
            covered[v] = true;
        } else if(bestPlan[v] == dist[v]){
            covered[v] = true;
            need++;
        }
    }

    cout << k - need << "\n";
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        @SuppressWarnings("unchecked")
        List<long[]>[] orig = new ArrayList[n + 1];
        @SuppressWarnings("unchecked")
        List<long[]>[] adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            orig[i] = new ArrayList<>();
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            long w = Long.parseLong(st.nextToken());
            orig[u].add(new long[]{v, w});
            orig[v].add(new long[]{u, w});
            adj[u].add(new long[]{v, w});
            adj[v].add(new long[]{u, w});
        }

        long[] bestPlan = new long[n + 1];
        Arrays.fill(bestPlan, Long.MAX_VALUE);
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            long d = Long.parseLong(st.nextToken());
            bestPlan[v] = Math.min(bestPlan[v], d);
        }

        for (int v = 2; v <= n; v++) {
            if (bestPlan[v] != Long.MAX_VALUE) {
                adj[1].add(new long[]{v, bestPlan[v]});
                adj[v].add(new long[]{1, bestPlan[v]});
            }
        }

        long INF = (long) 1e18;
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0, 1});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue;
            for (long[] edge : adj[u]) {
                int v = (int) edge[0];
                long w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }

        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i + 1;
        Arrays.sort(order, (a, b) -> Long.compare(dist[a], dist[b]));

        boolean[] covered = new boolean[n + 1];
        covered[1] = true;
        int need = 0;

        for (int v : order) {
            if (v == 1) continue;
            if (dist[v] >= INF) continue;
            boolean ok = false;
            for (long[] edge : orig[v]) {
                int u = (int) edge[0];
                long w = edge[1];
                if (covered[u] && dist[u] + w == dist[v]) { ok = true; break; }
            }
            if (ok) {
                covered[v] = true;
            } else if (bestPlan[v] == dist[v]) {
                covered[v] = true;
                need++;
            }
        }

        System.out.println(k - need);
    }
}