finding the shortest path in 01graph in oe v which is faster than dijkstra 01graph is the weighted graph with the weights equal to 0 or 1 link https codeforces comblogentry22276 weighted directed graph edge destinationvertex int weight int class adjacencylist get all the vertices adjacent to the given one return iterself graphvertex property def sizeself return self size def addedgeself fromvertex int tovertex int weight int if weight not in 0 1 raise valueerroredge weight must be either 0 or 1 if tovertex 0 or tovertex self size raise valueerrorvertex indexes must be in 0 size self graphfromvertex appendedgetovertex weight def getshortestpathself startvertex int finishvertex int int none queue dequestartvertex distances listint none none self size distancesstartvertex 0 while queue currentvertex queue popleft currentdistance distancescurrentvertex if currentdistance is none continue for edge in selfcurrentvertex newdistance currentdistance edge weight destvertexdistance distancesedge destinationvertex if isinstancedestvertexdistance int and newdistance destvertexdistance continue distancesedge destinationvertex newdistance if edge weight 0 queue appendleftedge destinationvertex else queue appendedge destinationvertex if distancesfinishvertex is none raise valueerrorno path from startvertex to finishvertex return distancesfinishvertex if name main import doctest doctest testmod weighted directed graph edge graph adjacency list get all the vertices adjacent to the given one g adjacencylist 2 g add_edge 0 1 0 g add_edge 1 0 1 list g 0 edge destination_vertex 1 weight 0 list g 1 edge destination_vertex 0 weight 1 g add_edge 0 1 2 traceback most recent call last valueerror edge weight must be either 0 or 1 g add_edge 0 2 1 traceback most recent call last valueerror vertex indexes must be in 0 size return the shortest distance from start_vertex to finish_vertex in 0 1 graph 1 1 1 0 3 6 7 8 1 0 v 0 0 1 9 10 1 v 0 1 2 4 5 0 1 1 g adjacencylist 11 g add_edge 0 1 0 g add_edge 0 3 1 g add_edge 1 2 0 g add_edge 2 3 0 g add_edge 4 2 1 g add_edge 4 5 1 g add_edge 4 6 1 g add_edge 5 9 0 g add_edge 6 7 1 g add_edge 7 8 1 g add_edge 8 10 1 g add_edge 9 7 0 g add_edge 9 10 1 g add_edge 1 2 2 traceback most recent call last valueerror edge weight must be either 0 or 1 g get_shortest_path 0 3 0 g get_shortest_path 0 4 traceback most recent call last valueerror no path from start_vertex to finish_vertex g get_shortest_path 4 10 2 g get_shortest_path 4 8 2 g get_shortest_path 0 1 0 g get_shortest_path 1 0 traceback most recent call last valueerror no path from start_vertex to finish_vertex
from __future__ import annotations

from collections import deque
from collections.abc import Iterator
from dataclasses import dataclass


@dataclass
class Edge:
    

    destination_vertex: int
    weight: int


class AdjacencyList:
    

    def __init__(self, size: int):
        self._graph: list[list[Edge]] = [[] for _ in range(size)]
        self._size = size

    def __getitem__(self, vertex: int) -> Iterator[Edge]:
        
        return iter(self._graph[vertex])

    @property
    def size(self):
        return self._size

    def add_edge(self, from_vertex: int, to_vertex: int, weight: int):
        
        if weight not in (0, 1):
            raise ValueError("Edge weight must be either 0 or 1.")

        if to_vertex < 0 or to_vertex >= self.size:
            raise ValueError("Vertex indexes must be in [0; size).")

        self._graph[from_vertex].append(Edge(to_vertex, weight))

    def get_shortest_path(self, start_vertex: int, finish_vertex: int) -> int | None:
        
        queue = deque([start_vertex])
        distances: list[int | None] = [None] * self.size
        distances[start_vertex] = 0

        while queue:
            current_vertex = queue.popleft()
            current_distance = distances[current_vertex]
            if current_distance is None:
                continue

            for edge in self[current_vertex]:
                new_distance = current_distance + edge.weight
                dest_vertex_distance = distances[edge.destination_vertex]
                if (
                    isinstance(dest_vertex_distance, int)
                    and new_distance >= dest_vertex_distance
                ):
                    continue
                distances[edge.destination_vertex] = new_distance
                if edge.weight == 0:
                    queue.appendleft(edge.destination_vertex)
                else:
                    queue.append(edge.destination_vertex)

        if distances[finish_vertex] is None:
            raise ValueError("No path from start_vertex to finish_vertex.")

        return distances[finish_vertex]


if __name__ == "__main__":
    import doctest

    doctest.testmod()