题目链接

小红修道路

题目描述

给定一个带权无向连通图和 条从顶点 1 出发的计划修建的道路。问最多可以删除多少条计划道路，使得从顶点 1 到所有其他顶点的最短路径长度，与全部 条道路都修建时的情况相比，保持不变。

解题思路

这个问题的核心是找出哪些计划道路是“不可或缺”的，然后从总数中减去这些必要的道路。

我们可以将问题分解为两个主要步骤：

  1. 确定最终的最短路径：首先，我们需要知道在最理想的情况下（即所有 条计划道路都修建后），从顶点 1 到其他所有顶点的最短路径长度是多少。这是一个典型的单源最短路径问题，由于所有边权非负，我们可以使用 Dijkstra 算法来解决。我们在包含原始边和所有计划边的完整图上运行 Dijkstra，得到最终的最短距离数组 。

  2. 识别必要的计划道路：对于一条计划道路 ，它什么时候是“必要的”？

    • 首先，这条路必须本身是一条最短路，即它的权值 必须等于顶点 1 到 的最终最短距离 。如果 ，说明存在其他更短的路径，这条计划道路就毫无用处，可以删除。
    • 其次，即使 ，这条路也未必是必要的。可能还存在另一条不依赖此路的、长度同样为 的路径。这种替代路径的最后一段必然是一条原始图中的边，例如 。这个条件可以用 Dijkstra 算法的松弛条件来验证：是否存在一个 在原始图中的邻居 ，满足 。

综合以上两点，一条连接到顶点 的计划道路是必要的，当且仅当：

  1. 所有连接到 的计划道路中，权值最小的那条等于 。
  2. 并且，对于所有在原始图中与 相连的邻居 ，都不满足 。

换言之，如果到达顶点 的最短路径无法通过原始图中的任何一条边来“拼接”完成，那么它就必须直接依赖于一条从顶点 1 出发的计划道路。

算法流程

  1. 构建包含原始边和所有计划边的完整图。
  2. 在完整图上从顶点 1 运行 Dijkstra 算法，计算出 数组。
  3. 初始化必要道路计数 necessary_roads = 0。
  4. 遍历每一个从 1 出发的计划道路 。
  5. 如果一条计划道路满足 ，则将其视为一条“候选必要”道路。
  6. 对每一个有“候选必要”道路的顶点 进行检查： a. 判断是否存在一条原始边 满足 。 b. 如果不存在这样的原始边，说明要达到 的最短距离，必须依赖一条从 1 直连到 的计划道路。因此，我们将 necessary_roads 加一。注意，对于同一个顶点 ，即使有多条满足条件的计划道路，我们也只计数一次，因为只需保留其中一条即可。
  7. 最终答案为 。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;
using ll = long long;
using P = pair<ll, int>;

const ll INF = 1e18;

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

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

    vector<vector<P>> base_adj(n + 1);
    vector<vector<P>> full_adj(n + 1);
    vector<P> planned_edges;

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

    for (int i = 0; i < k; ++i) {
        int u, w;
        cin >> u >> w;
        planned_edges.push_back({u, w});
        full_adj[1].push_back({u, w});
        full_adj[u].push_back({1, w});
    }

    vector<ll> d_final(n + 1, INF);
    priority_queue<P, vector<P>, greater<P>> pq;

    d_final[1] = 0;
    pq.push({0, 1});

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

        if (dist > d_final[u]) {
            continue;
        }

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

    int necessary_roads = 0;
    map<int, bool> dest_needs_planned_road;

    for (const auto& edge : planned_edges) {
        int u = edge.first;
        int w = edge.second;
        if (d_final[u] == (ll)w) {
             dest_needs_planned_road[u] = true;
        }
    }
    
    for(auto const& [u, needs_check] : dest_needs_planned_road){
        if(needs_check){
            bool achievable_by_base = false;
            for(const auto& base_edge : base_adj[u]){
                int v = base_edge.first;
                int w = base_edge.second;
                if(d_final[v] + w == d_final[u]){
                    achievable_by_base = true;
                    break;
                }
            }
            if(!achievable_by_base){
                necessary_roads++;
            }
        }
    }

    cout << k - necessary_roads << endl;

    return 0;
}

import java.util.*;

public class Main {
    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    static class State implements Comparable<State> {
        long dist;
        int u;

        State(long dist, int u) {
            this.dist = dist;
            this.u = u;
        }

        @Override
        public int compareTo(State other) {
            return Long.compare(this.dist, other.dist);
        }
    }

    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>> baseAdj = new ArrayList<>();
        List<List<Edge>> fullAdj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            baseAdj.add(new ArrayList<>());
            fullAdj.add(new ArrayList<>());
        }

        List<Edge> plannedEdges = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            baseAdj.get(u).add(new Edge(v, w));
            baseAdj.get(v).add(new Edge(u, w));
            fullAdj.get(u).add(new Edge(v, w));
            fullAdj.get(v).add(new Edge(u, w));
        }

        for (int i = 0; i < k; i++) {
            int u = sc.nextInt();
            int w = sc.nextInt();
            plannedEdges.add(new Edge(u, w));
            fullAdj.get(1).add(new Edge(u, w));
            fullAdj.get(u).add(new Edge(1, w));
        }

        long[] dFinal = new long[n + 1];
        Arrays.fill(dFinal, Long.MAX_VALUE);
        PriorityQueue<State> pq = new PriorityQueue<>();

        dFinal[1] = 0;
        pq.offer(new State(0, 1));

        while (!pq.isEmpty()) {
            State current = pq.poll();
            long dist = current.dist;
            int u = current.u;

            if (dist > dFinal[u]) {
                continue;
            }

            for (Edge edge : fullAdj.get(u)) {
                int v = edge.to;
                int w = edge.weight;
                if (dFinal[u] + w < dFinal[v]) {
                    dFinal[v] = dFinal[u] + w;
                    pq.offer(new State(dFinal[v], v));
                }
            }
        }

        int necessaryRoads = 0;
        Set<Integer> candidateDests = new HashSet<>();
        for(Edge edge : plannedEdges){
            if(dFinal[edge.to] == edge.weight){
                candidateDests.add(edge.to);
            }
        }

        for(int u : candidateDests){
            boolean achievableByBase = false;
            for(Edge baseEdge : baseAdj.get(u)){
                int v = baseEdge.to;
                int w = baseEdge.weight;
                if(dFinal[v] != Long.MAX_VALUE && dFinal[v] + w == dFinal[u]){
                    achievableByBase = true;
                    break;
                }
            }
            if(!achievableByBase){
                necessaryRoads++;
            }
        }
        
        System.out.println(k - necessaryRoads);
    }
}

import sys
import heapq

def main():
    input = sys.stdin.readline
    n, m, k = map(int, input().split())

    base_adj = [[] for _ in range(n + 1)]
    full_adj = [[] for _ in range(n + 1)]
    planned_edges = []

    for _ in range(m):
        u, v, w = map(int, input().split())
        base_adj[u].append((v, w))
        base_adj[v].append((u, w))
        full_adj[u].append((v, w))
        full_adj[v].append((u, w))

    for _ in range(k):
        u, w = map(int, input().split())
        planned_edges.append((u, w))
        full_adj[1].append((u, w))
        full_adj[u].append((1, w))

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

    while pq:
        dist, u = heapq.heappop(pq)

        if dist > d_final[u]:
            continue

        for v, w in full_adj[u]:
            if d_final[u] + w < d_final[v]:
                d_final[v] = d_final[u] + w
                heapq.heappush(pq, (d_final[v], v))
    
    necessary_roads = 0
    candidate_dests = set()
    for u, w in planned_edges:
        if d_final[u] == w:
            candidate_dests.add(u)

    for u in candidate_dests:
        achievable_by_base = False
        for v, w_base in base_adj[u]:
            if d_final[v] != float('inf') and d_final[v] + w_base == d_final[u]:
                achievable_by_base = True
                break
        if not achievable_by_base:
            necessary_roads += 1
            
    print(k - necessary_roads)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：Dijkstra 算法
  • 时间复杂度：。主要开销是使用优先队列的 Dijkstra 算法，图中有 个顶点和 条边。
  • 空间复杂度：，用于存储图的邻接表和 Dijkstra 算法所需的距离数组等。