京东 · 图 · 算法编程题
京东 图 n ≤ 1e5 时限 1 秒 / 256 MB

题目描述

小红有一个 n 个点 m 条边的无向图，每条边有一个权值 w_i 。小红现在计划修 k 条双向道路，起点是 1 号点，终点是其他顶点。假设修了这 k 条路后，从 1 号点到其他点的距离为 d_i ，小红想知道，可以少修多少条路，使得从 1 号点到其他点的距离仍然为 d_i 。

输入输出

输入描述
第一行三个整数 n,m,k ，表示点数，边数，以及小红计划修的路数。
接下来 m 行，每行三个整数 u_i,v_i,w_i ，表示一条边的两个端点以及权值。
接下来 k 行，每行两个整数 p_i, s_i ，表示计划修从 1 号点到 p_i 号点的一条路，长度为 s_i 。
1 ≤ n, m, k ≤ 10^5
1 ≤ u_i, v_i, p_i ≤ 10^5
1 ≤ w_i, s_i ≤ 10^9
输出描述
输出一个整数，表示可以少修的路数。

样例共 1 组

样例 1 · 从 1 号点到 2 号点的距离为 2，修路不能改变最短距离，两条路都可以不修。
输入
2 2 2
1 2 2
2 1 3
2 2
2 3
输出
2

算法解析依据充分

考点：图 · 堆

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e5，m ≤ 1e5，k ≤ 1e5
  • 元素值域：w_i ≤ 1e9，s_i ≤ 1e9，u_i ≤ 1e5（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：图

把关系抽象成点与边，再按问的类型选遍历/最短路/连通性算法。

思路框架（图 通法 · 非本题专属）

  1. 建图：邻接表（稀疏）或邻接矩阵（稠密）。
  2. 问「最少几步 / 最短路径」且边权为 1 → BFS。
  3. 问「是否连通 / 需要加几条边连通」→ 并查集 / 连通块计数。
  4. 问「带权最短路」→ Dijkstra（非负权）或 Floyd（点数小、多源）。
  5. 问「依赖顺序」→ 拓扑排序。

实现要点：注意是有向图还是无向图，无向图加边记得双向。

复杂度：时间 O(V+E) 遍历 / O(E log V) Dijkstra ｜ 空间 O(V+E)

该范式的通法易错点

  • 无向图只加了单向边。
  • BFS 入队时没标记访问，导致重复入队。

对照本题

  • 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 2 2 2 / 1 2 2 / 2 1 3 / 2 2 / 2 3 → 输出 2

从 1 号点到 2 号点的距离为 2，修路不能改变最短距离，两条路都可以不修。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年秋招-京东-技术通用岗位-第十批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解