Implement an Algorithm Function | Dataford Interview Questions

Implement a function to solve a specific algorithmic problem.

Given a directed weighted graph, find the minimum cost to travel from start to end when one edge may be traversed at half price, rounded down. The discount may be used at most once, and return -1 if the destination is unreachable.

Use def minimum_cost(n, edges, start, end):. n is the number of vertices labeled 0 through n - 1; each edge is [source, destination, cost]. Return an integer.

Examples: n = 3, edges = [[0,1,5],[1,2,5]], start = 0, end = 2 returns 7. A path of cost 5 + 5 becomes 2 + 5. If start == end, return 0.

Constraints: 1 <= n <= 1000, 0 <= edges.length <= 5000, edge costs are nonnegative integers, and parallel edges may exist.

Constraints

1 <= n <= 1000
0 <= edges.length <= 5000
0 <= source, destination < n
0 <= cost <= 10^9
The graph is directed
Parallel edges may exist

Function Signature

def minimum_cost(n, edges, start, end):

Your question is Implement an Algorithm Function. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem