<p>You are given an array <code>start</code> where <code>start = [startX, startY]</code> represents your initial position <code>(startX, startY)</code> in a 2D space. You are also given the array <code>target</code> where <code>target = [targetX, targetY]</code> represents your target position <code>(targetX, targetY)</code>.</p>

<p>The <strong>cost</strong> of going from a position <code>(x1, y1)</code> to any other position in the space <code>(x2, y2)</code> is <code>|x2 - x1| + |y2 - y1|</code>.</p>

<p>There are also some <strong>special roads</strong>. You are given a 2D array <code>specialRoads</code> where <code>specialRoads[i] = [x1<sub>i</sub>, y1<sub>i</sub>, x2<sub>i</sub>, y2<sub>i</sub>, cost<sub>i</sub>]</code> indicates that the <code>i<sup>th</sup></code> special road goes in <strong>one direction</strong> from <code>(x1<sub>i</sub>, y1<sub>i</sub>)</code> to <code>(x2<sub>i</sub>, y2<sub>i</sub>)</code> with a cost equal to <code>cost<sub>i</sub></code>. You can use each special road any number of times.</p>

<p>Return the <strong>minimum</strong> cost required to go from <code>(startX, startY)</code> to <code>(targetX, targetY)</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<ol>
	<li>(1,1) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1.</li>
	<li>(1,2) to (3,3). Use <code><span class="example-io">specialRoads[0]</span></code><span class="example-io"> with</span><span class="example-io"> the cost 2.</span></li>
	<li><span class="example-io">(3,3) to (3,4) with a cost of |3 - 3| + |4 - 3| = 1.</span></li>
	<li><span class="example-io">(3,4) to (4,5). Use </span><code><span class="example-io">specialRoads[1]</span></code><span class="example-io"> with the cost</span><span class="example-io"> 1.</span></li>
</ol>

<p><span class="example-io">So the total cost is 1 + 2 + 1 + 1 = 5.</span></p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">start = [3,2], target = [5,7], specialRoads = [[5,7,3,2,1],[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]</span></p>

<p><strong>Output:</strong> <span class="example-io">7</span></p>

<p><strong>Explanation:</strong></p>

<p>It is optimal not to use any special edges and go directly from the starting to the ending position with a cost |5 - 3| + |7 - 2| = 7.</p>

<p>Note that the <span class="example-io"><code>specialRoads[0]</code> is directed from (5,7) to (3,2).</span></p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">start = [1,1], target = [10,4], specialRoads = [[4,2,1,1,3],[1,2,7,4,4],[10,3,6,1,2],[6,1,1,2,3]]</span></p>

<p><strong>Output:</strong> <span class="example-io">8</span></p>

<p><strong>Explanation:</strong></p>

<ol>
	<li>(1,1) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1.</li>
	<li>(1,2) to (7,4). Use <code><span class="example-io">specialRoads[1]</span></code><span class="example-io"> with the cost</span><span class="example-io"> 4.</span></li>
	<li>(7,4) to (10,4) with a cost of |10 - 7| + |4 - 4| = 3.</li>
</ol>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>start.length == target.length == 2</code></li>
	<li><code>1 &lt;= startX &lt;= targetX &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= startY &lt;= targetY &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= specialRoads.length &lt;= 200</code></li>
	<li><code>specialRoads[i].length == 5</code></li>
	<li><code>startX &lt;= x1<sub>i</sub>, x2<sub>i</sub> &lt;= targetX</code></li>
	<li><code>startY &lt;= y1<sub>i</sub>, y2<sub>i</sub> &lt;= targetY</code></li>
	<li><code>1 &lt;= cost<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

# minimum-cost-of-a-path-with-special-roads
import heapq
from typing import List, Dict, Set, Tuple


def str_to_coords(s: str) -> Tuple[int, int]:
    return tuple(map(int, s.split(',')))


def euclidian_cost(beg_str: str, end_str: str) -> int:
    beg_x, beg_y = str_to_coords(beg_str)
    end_x, end_y = str_to_coords(end_str)
    return abs(beg_x - end_x) + abs(beg_y - end_y)


class Graph:
    def __init__(self):
        self.vertices: Set[str] = set()
        self.graph: Dict[str, Dict[str, int]] = dict()

    def add_edge(self, beg: str, end: str, weight: int) -> None:
        self.vertices.add(beg)
        self.vertices.add(end)
        self.graph[beg] = self.graph.get(beg, dict())
        if end not in self.graph[beg] or weight < self.graph[beg][end]:
            self.graph[beg][end] = weight

    @staticmethod
    def build_graph(beg_str: str, end_str: str, special_edges: List[List[int]]) -> "Graph":
        graph = Graph()
        graph.add_edge(beg_str, end_str, euclidian_cost(beg_str, end_str))
        # reformat {beg -> {end -> cost, ...}, ...}
        for e in special_edges:
            e_beg, e_end, e_cost = f"{e[0]},{e[1]}", f"{e[2]},{e[3]}", e[4]
            graph.add_edge(e_beg, e_end, e_cost)
        # build edges between both
        vertices_list = list(graph.vertices)
        for v in vertices_list:
            graph.add_edge(v, v, 0)
        for i in range(len(vertices_list) - 1):
            for j in range(i + 1, len(vertices_list)):
                e_beg, e_end = vertices_list[i], vertices_list[j]
                e_cost = euclidian_cost(e_beg, e_end)
                # edge from beg -> end
                graph.add_edge(e_beg, e_end, e_cost)
                graph.add_edge(e_end, e_beg, e_cost)
        # return  final graph
        return graph


def min_cost_v3(beg_str: str, end_str: str, graph: Dict[str, Dict[str, int]]) -> int:
    # initialize data structures
    visited = set()
    nodes_costs: Dict[str, int] = {beg_str: 0}
    priority_queue = []
    max_total_cost = euclidian_cost(beg_str, end_str)
    heapq.heappush(priority_queue, (0, beg_str))
    # run djikstra's
    while priority_queue:
        curr_cost, curr_node = heapq.heappop(priority_queue)
        # return if reached target
        if curr_node == end_str:
            return nodes_costs[curr_node]
        # skip, already found min
        if curr_node in visited:
            continue
        # mark visited
        visited.add(curr_node)
        # skip if exceeded brute force cost
        if max_total_cost < nodes_costs[curr_node]:
            continue
        # explore neighbors
        neighbors = [(next_node, cost) for next_node, cost in graph.get(curr_node, dict()).items() if
                     next_node not in visited]
        # enqueue neighbors
        for next_node, cost in neighbors:
            next_cost = nodes_costs[curr_node] + cost
            if next_node not in nodes_costs or next_cost < nodes_costs[next_node]:
                nodes_costs[next_node] = next_cost
                heapq.heappush(priority_queue, (next_cost, next_node))
    # never found target
    return nodes_costs.get(end_str, max_total_cost)


class Solution:

    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
        # reformat {beg -> {end -> cost, ...}, ...}
        start_str = f"{start[0]},{start[1]}"
        target_str = f"{target[0]},{target[1]}"
        graph: Graph = Graph.build_graph(start_str, target_str, specialRoads)
        # explore cardinal directions
        cost = min_cost_v3(beg_str=start_str, end_str=target_str, graph=graph.graph)
        return cost
785