42. Shortest Path with Processing Delays at Nodes

Origin: HackerRank Prep Kit #42

题目描述

给定 n 个节点、每个节点的处理时间（handling_times）、有向加权边、源节点 source，求从 source 到所有节点的最短路径，包含中间节点的处理延迟。返回数组，元素 i 为到达节点 i 的最短时间，不可达返回 -1。

关键：中间节点的 handling time 计入总时间，但源节点和终点节点不计。

示例

Example 1

Input: n=3, handling_times=[1,2,3], edges=[(0,1,4),(1,2,5),(0,2,10)], source=0

Output: [0, 4, 10]

Explanation:

• 节点 0：起点，时间 0
• 节点 1：0→1 直达，travel=4，无中间节点，total=4
• 节点 2：0→2 直达 travel=10（无中间）；或 0→1→2 travel=4+5=9 + handling[1]=2 = 11。取最小 10

Example 2

Input: n=5, handling_times=[0,5,2,3,0], edges=[(0,1,2),(0,2,8),(1,3,7),(2,3,1),(1,4,15),(3,4,3)], source=0

Output: [0, 2, 8, 11, 17]

Sample Input 0

1 1 0 0 0 0 0

Output: 0

Sample Input 1

2 2 1 2 1 1 3 0 1 3 0

Output: 0 3

Sample Input 2

3 3 1 2 3 3 3 3 0 1 4 1 2 5 0 2 10 0

Output: 0 4 10

约束

• 1 <= n <= 100000
• handling_times.length == n

关键信息

• Dijkstra 变体：边权 = travel time + 目标节点的 handling time（如果不是终点）
• 中间节点的 handling time 计入，源节点和终点不计
• 不可达返回 -1

Resolution

⏭️ 跳过：Dijkstra 最短路径，前端/Agent 面试出现频率低，时间花在高频题型上更值。