#3650

Minimum Cost Path with Edge Reversals

specialist · 690 · lc medium +30 · 61.8% accepted · 456 likes · top 62%

Description

A directed weighted graph has n nodes (0 to n-1) and edges [u, v, w]. Each node has a one-time switch: upon arriving at node u, if unused, the switch may reverse one incoming edge v → u to u → v and traverse it immediately at cost 2 * w. Forward traversals cost w. Find the minimum total travel cost from node 0 to node n-1, or -1 if unreachable.

Code

1

2

3

class Solution:
    def minCost(self, n: int, edges: List[List[int]]) -> int:

class Solution:
    def minCost(self, n: int, edges: List[List[int]]) -> int: