题目链接

小红修道路

题目描述

给定一个 个点 条边的带权无向图。现在计划修建 条新的双向道路，所有新路都以 1 号点为起点。

假设修建了所有 条新路后，从 1 号点到各点的最短距离为 。问题是，可以不修建这 条路中的多少条，仍能使得从 1 号点到各点的最短距离保持为 ？

解题思路

这是一个基于单源最短路径的图论问题。核心思想是先确定最终的最短路径状态，然后判断每条计划修建的道路对于维持这个状态是否是“必要”的。

1. 确定最终最短路径

首先，我们需要知道如果所有 条路都修建了，从 1 号点出发的全局最短路径是怎样的。

  • 构建一个“完整图”，该图包含原始的 条边和所有计划的 条边。
  • 从 1 号点开始，对这个完整图运行一次 Dijkstra 算法，计算出从 1 到所有其他点的最短距离 dist[i]。这个 dist 数组就是我们必须维持的目标最短距离。

2. 判断道路的必要性

一条道路是“必要”的，意味着它是构成某条最短路径的唯一关键部分。如果一条道路不是必要的，那它就是“多余”的，可以不修。

根据 Dijkstra 算法的最短路径性质，一条从 u到 v 权重为 w 的边是 1 -> v 最短路径的最后一段，当且仅当 dist[u] + w == dist[v]。

我们可以为图中每个节点 v 计算一个“最短路径入度”，即满足 dist[u] + w == dist[v] 的入边 (u, v) 的数量。这个值可以在 Dijkstra 跑完后，遍历所有边一次来计算。

现在，我们可以遍历每一条计划修建的道路 (1, v)，其长度为 l：

  • 情况一：l > dist[v] 这条计划的路比实际到 v 的最短路径还要长。它不可能出现在任何最短路径上，因此是多余的。

  • 情况二：l == dist[v] 这条路是到达 v 的一条有效最短路径。现在需要判断它是否是唯一的。

    • 如果 v 的“最短路径入度”大于 1，意味着除了 (1, v) 这条路之外，还存在至少一条其他的路径能够以最短距离到达 v。因此，(1, v) 这条路不是唯一的，是多余的。
    • 如果 v 的“最短路径入度”等于 1，这意味着 (1, v) 是以最短距离到达 v 的唯一方式。移除它会导致 dist[v] 变大。因此，这条路是必要的。

最后，统计所有多余的道路数量即可。

代码

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, p;
    cin >> n >> m >> p;

    vector<vector<pair<int, int>>> adj(n + 1);
    vector<tuple<int, int, int>> all_edges;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        all_edges.emplace_back(u, v, w);
    }

    vector<pair<int, int>> planned_roads(p);
    for (int i = 0; i < p; ++i) {
        int v, l;
        cin >> v >> l;
        adj[1].push_back({v, l});
        adj[v].push_back({1, l});
        planned_roads[i] = {v, l};
    }

    vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    vector<int> sp_in_degree(n + 1, 0);
    for (const auto& edge : all_edges) {
        int u, v, w;
        tie(u, v, w) = edge;
        if (dist[u] + w == dist[v]) sp_in_degree[v]++;
        if (dist[v] + w == dist[u]) sp_in_degree[u]++;
    }
    for (const auto& road : planned_roads) {
        int v = road.first;
        int l = road.second;
        if (dist[1] + l == dist[v]) sp_in_degree[v]++;
    }
    
    int unnecessary_roads = 0;
    for (const auto& road : planned_roads) {
        int v = road.first;
        long long l = road.second;
        if (l > dist[v]) {
            unnecessary_roads++;
        } else if (l == dist[v]) {
            if (sp_in_degree[v] > 1) {
                unnecessary_roads++;
            }
        }
    }

    cout << unnecessary_roads << endl;

    return 0;
}

import java.util.*;

public class Main {
    static final long INF = (long) 1e18;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int p = sc.nextInt();

        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        
        List<int[]> allEdges = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            adj.get(u).add(new int[]{v, w});
            adj.get(v).add(new int[]{u, w});
            allEdges.add(new int[]{u, v, w});
        }

        int[][] plannedRoads = new int[p][2];
        for (int i = 0; i < p; i++) {
            int v = sc.nextInt();
            int l = sc.nextInt();
            adj.get(1).add(new int[]{v, l});
            adj.get(v).add(new int[]{1, l});
            plannedRoads[i][0] = v;
            plannedRoads[i][1] = l;
        }

        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.add(new long[]{0, 1});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long d = current[0];
            int u = (int) current[1];

            if (d > dist[u]) continue;

            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                int w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.add(new long[]{dist[v], v});
                }
            }
        }

        int[] spInDegree = new int[n + 1];
        for (int[] edge : allEdges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist[u] != INF && dist[u] + w == dist[v]) spInDegree[v]++;
            if (dist[v] != INF && dist[v] + w == dist[u]) spInDegree[u]++;
        }
        for (int[] road : plannedRoads) {
            int v = road[0];
            int l = road[1];
            if (dist[1] + l == dist[v]) spInDegree[v]++;
        }
        
        int unnecessaryRoads = 0;
        for (int[] road : plannedRoads) {
            int v = road[0];
            long l = road[1];
            if (l > dist[v] || (l == dist[v] && spInDegree[v] > 1)) {
                unnecessaryRoads++;
            }
        }

        System.out.println(unnecessaryRoads);
    }
}

import heapq
import sys

def solve():
    n, m, p = map(int, sys.stdin.readline().split())
    
    adj = [[] for _ in range(n + 1)]
    all_edges = []

    for _ in range(m):
        u, v, w = map(int, sys.stdin.readline().split())
        adj[u].append((v, w))
        adj[v].append((u, w))
        all_edges.append((u, v, w))

    planned_roads = []
    for _ in range(p):
        v, l = map(int, sys.stdin.readline().split())
        adj[1].append((v, l))
        adj[v].append((1, l))
        planned_roads.append((v, l))

    dist = [float('inf')] * (n + 1)
    dist[1] = 0
    pq = [(0, 1)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    sp_in_degree = [0] * (n + 1)
    for u, v, w in all_edges:
        if dist[u] != float('inf') and dist[u] + w == dist[v]:
            sp_in_degree[v] += 1
        if dist[v] != float('inf') and dist[v] + w == dist[u]:
            sp_in_degree[u] += 1
    
    for v, l in planned_roads:
        if dist[1] + l == dist[v]:
            sp_in_degree[v] += 1

    unnecessary_roads = 0
    for v, l in planned_roads:
        if l > dist[v]:
            unnecessary_roads += 1
        elif l == dist[v] and sp_in_degree[v] > 1:
            unnecessary_roads += 1
            
    print(unnecessary_roads)

solve()

算法及复杂度

  • 算法：Dijkstra 算法
  • 时间复杂度：，其中 分别是点数、原始边数和计划边数。复杂度主要由在完整图上运行 Dijkstra 算法决定。
  • 空间复杂度：，用于存储图的邻接表和 dist 数组。