Tap here to switch tabs
Problem
Submissions

Problem: Minimum Time to Reach Target With Limited Power

Minimum Time to Reach Target With Limited Power asks for the fast route in a weighted directed graph with node power costs. Time ties favor more power; return time and remaining power, or negative ones if unreachable.

Statement

You are given an integer n representing the number of nodes in a directed weighted graph, labeled from 00 to n −1- 1.

You are also given:

  • A 2D2\text{D} integer array edges where edges[i] = [ui,vi,tiu_i, v_i, t_i] indicates a directed edge from node uiu_i to node viv_i with a traversal time of tit_i.

  • An integer power representing the initial power available for traversal.

  • An integer array cost of length n, where cost[i] is the amount of power consumed when leaving node i.

  • Two integers source and target.

A signal starts at source with power units of power. To traverse from a node u to an adjacent node v, the signal consumes cost[u] power. The destination node target does not consume any power upon arrival. The total power consumed along any path cannot exceed power.

If source == target, the time taken is 00 and no power is consumed.

Find a path from source to target that minimizes the total traversal time. If there are multiple such paths with the same minimum time, choose the one that maximizes the remaining power.

Return an integer array [min_time,max_power\text{min\_time}, \text{max\_power}] containing the minimum time to reach target and the maximum remaining power. If no valid path exists from source to target, return [−1,−1-1, -1].

Constraints:

  • 1≤1 \leq n ≤1000\leq 1000

  • 0≤0 \leq edges.length ≤1000\leq 1000

  • edges[i] = [ui,vi,tiu_i, v_i, t_i]

  • 0≤ui,vi≤0 \leq u_i, v_i \leq n −1- 1

  • 1≤ti≤1091 \leq t_i \leq 10^9

  • 1≤1 \leq power ≤1000\leq 1000

  • cost.length ==== n

  • 1≤1 \leq cost[i] ≤2000\leq 2000

  • 0≤0 \leq source, target ≤\leq n −1- 1

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Time to Reach Target With Limited Power

Minimum Time to Reach Target With Limited Power asks for the fast route in a weighted directed graph with node power costs. Time ties favor more power; return time and remaining power, or negative ones if unreachable.

Statement

You are given an integer n representing the number of nodes in a directed weighted graph, labeled from 00 to n −1- 1.

You are also given:

  • A 2D2\text{D} integer array edges where edges[i] = [ui,vi,tiu_i, v_i, t_i] indicates a directed edge from node uiu_i to node viv_i with a traversal time of tit_i.

  • An integer power representing the initial power available for traversal.

  • An integer array cost of length n, where cost[i] is the amount of power consumed when leaving node i.

  • Two integers source and target.

A signal starts at source with power units of power. To traverse from a node u to an adjacent node v, the signal consumes cost[u] power. The destination node target does not consume any power upon arrival. The total power consumed along any path cannot exceed power.

If source == target, the time taken is 00 and no power is consumed.

Find a path from source to target that minimizes the total traversal time. If there are multiple such paths with the same minimum time, choose the one that maximizes the remaining power.

Return an integer array [min_time,max_power\text{min\_time}, \text{max\_power}] containing the minimum time to reach target and the maximum remaining power. If no valid path exists from source to target, return [−1,−1-1, -1].

Constraints:

  • 1≤1 \leq n ≤1000\leq 1000

  • 0≤0 \leq edges.length ≤1000\leq 1000

  • edges[i] = [ui,vi,tiu_i, v_i, t_i]

  • 0≤ui,vi≤0 \leq u_i, v_i \leq n −1- 1

  • 1≤ti≤1091 \leq t_i \leq 10^9

  • 1≤1 \leq power ≤1000\leq 1000

  • cost.length ==== n

  • 1≤1 \leq cost[i] ≤2000\leq 2000

  • 0≤0 \leq source, target ≤\leq n −1- 1