<p>You are given an undirected weighted graph of <code>n</code> nodes numbered from 0 to <code>n - 1</code>. The graph consists of <code>m</code> edges represented by a 2D array <code>edges</code>, where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>, w<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> with weight <code>w<sub>i</sub></code>.</p>

<p>Consider all the shortest paths from node 0 to node <code>n - 1</code> in the graph. You need to find a <strong>boolean</strong> array <code>answer</code> where <code>answer[i]</code> is <code>true</code> if the edge <code>edges[i]</code> is part of <strong>at least</strong> one shortest path. Otherwise, <code>answer[i]</code> is <code>false</code>.</p>

<p>Return the array <code>answer</code>.</p>

<p><strong>Note</strong> that the graph may not be connected.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/03/05/graph35drawio-1.png" style="height: 129px; width: 250px;" />
<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[true,true,true,false,true,true,true,false]</span></p>

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

<p>The following are <strong>all</strong> the shortest paths between nodes 0 and 5:</p>

<ul>
	<li>The path <code>0 -&gt; 1 -&gt; 5</code>: The sum of weights is <code>4 + 1 = 5</code>.</li>
	<li>The path <code>0 -&gt; 2 -&gt; 3 -&gt; 5</code>: The sum of weights is <code>1 + 1 + 3 = 5</code>.</li>
	<li>The path <code>0 -&gt; 2 -&gt; 3 -&gt; 1 -&gt; 5</code>: The sum of weights is <code>1 + 1 + 2 + 1 = 5</code>.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/03/05/graphhhh.png" style="width: 185px; height: 136px;" />
<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 4, edges = [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[true,false,false,true]</span></p>

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

<p>There is one shortest path between nodes 0 and 3, which is the path <code>0 -&gt; 2 -&gt; 3</code> with the sum of weights <code>1 + 2 = 3</code>.</p>
</div>

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

<ul>
	<li><code>2 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>m == edges.length</code></li>
	<li><code>1 &lt;= m &lt;= min(5 * 10<sup>4</sup>, n * (n - 1) / 2)</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li><code>1 &lt;= w<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
	<li>There are no repeated edges.</li>
</ul>

"""
Dijkstra algorightm to find shortest path from 0 to n-1: O(E*logV)
During algorithm:
- picking vertext with minimal distance from queue
- update distances to other vertices from this vertex: if d[u] + weight < d[v]: d[v] = d[u] + weight. Add to queue if updated
- put parent index during update to recover the path

Modified algorithm: support array of previous vertices which can lead to shortest path prev[v]
if d[u] + weight == d[v]: add u to the array prev[v]
if d[u] + weight < d[v]: clear prev[v] and add add u

prev - represends unweighted directed graph
Launch BFS on top of this graph
Mark transposed edges from BFS in original array as True
"""
import heapq
from dataclasses import dataclass, field
from collections import deque

@dataclass
class Edge:
    to: int
    weight: int
    idx: int


@dataclass(order=True)
class QueueElement:
    dist: int = field(compare=True)
    vertex: int = field(compare=False)


@dataclass
class PassRecoveryElement:
    vertex: int
    edge: int


class DijkstraSolver:
    def __init__(self, graph: List[List[Edge]]):
        self.graph = graph
        self.distances = [None for _ in range(len(graph))]
        self.pass_recovery = [None for _ in range(len(graph))]

    def solve(self):
        self.distances[0] = 0
        self.pass_recovery[0] = []
        queue = [QueueElement(dist=0, vertex=0)]
        while queue:
            element = heapq.heappop(queue)
            # Late deletion of updated elements in queue 
            # since we don't remove old instances after distance update
            if element.dist != self.distances[element.vertex]:
                continue

            for edge in self.graph[element.vertex]:
                distance_candidate = self.distances[element.vertex] + edge.weight
                if self.distances[edge.to] is None or distance_candidate < self.distances[edge.to]:
                    self.distances[edge.to] = distance_candidate
                    heapq.heappush(queue, QueueElement(dist=distance_candidate, vertex=edge.to))
                    self.pass_recovery[edge.to] = [
                        PassRecoveryElement(vertex=element.vertex, edge=edge.idx)
                    ]
                elif distance_candidate == self.distances[edge.to]:
                    self.pass_recovery[edge.to].append(
                        PassRecoveryElement(vertex=element.vertex, edge=edge.idx)
                    )


class Solution:
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        graph = [[] for _ in range(n)]
        for idx, (u, v, w) in enumerate(edges):
            graph[u].append(Edge(to=v, weight=w, idx=idx))
            graph[v].append(Edge(to=u, weight=w, idx=idx))
        
        solver = DijkstraSolver(graph)
        solver.solve()

        answer = [False for _ in range(len(edges))]

        if solver.pass_recovery[n - 1] is None:
            return answer
        
        queue = deque()
        queue.appendleft(n - 1)
        used_vertices = [False for _ in range(n)]

        while queue:
            current = queue.popleft()
            if used_vertices[current]:
                continue

            for previous in solver.pass_recovery[current]:
                answer[previous.edge] = True
                queue.append(previous.vertex)
            
            used_vertices[current] = True
        
        return answer

60100