Shortest Path with Discount

Easy

0/40

Contributed by

0 upvote

Asked in company

Problem statement

You are given a directed weighted graph with N nodes and M edges. The nodes are numbered from 1 to N. Each edge has a positive weight, representing the cost to travel between two nodes.

You have a special discount coupon that you can apply to at most one edge in the entire graph. This coupon reduces the weight of the chosen edge to half its value (using floor division, i.e., newweight = floor(originalweight / 2)).

Your task is to find the minimum possible cost to travel from the starting node 1 to the destination node N. You can choose to use the coupon on any single edge, or not use it at all if the original shortest path is already optimal.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two space-separated integers: N (number of nodes) and M (number of edges).

The next M lines each describe an edge with three space-separated integers: u, v, and w. This represents a directed edge from node u to node v with a weight of w.

Output Format:

The output should be a single integer representing the minimum cost to travel from node 1 to node N.

Note:

Nodes are 1-indexed.

All edge weights are positive.

If you apply the discount to an edge of weight w, its new weight becomes w / 2 (integer division).

If node N is unreachable from node 1, the cost is considered infinite. In this problem, it's guaranteed that a path exists.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

There are two main paths from node 1 to node 4:

Path A: 1 -> 2 -> 4. Original cost = 10 + 10 = 20.
Path B: 1 -> 3 -> 4. Original cost = 100 + 10 = 110.

The original shortest path costs 20.

Let's consider using the discount coupon:
- Discount on edge 1 -> 2: Path A cost becomes (10 / 2) + 10 = 5 + 10 = 15.
- Discount on edge 2 -> 4: Path A cost becomes 10 + (10 / 2) = 10 + 5 = 15.
- Discount on edge 1 -> 3: Path B cost becomes (100 / 2) + 10 = 50 + 10 = 60.
- Discount on edge 3 -> 4: Path B cost becomes 100 + (10 / 2) = 100 + 5 = 105.

=> The minimum cost achievable is 15.

Expected Time Complexity:

The expected time complexity is O(M * log N).

Constraints:

2 <= N <= 10^5
1 <= M <= 2 * 10^5
1 <= u, v <= N
1 <= w <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Two-Pass Dijkstra on Forward and Reversed Graphs

Time Complexity

Space Complexity

(100% EXP penalty)

Shortest Path with Discount

Console