"""
CS 20P: Shortest paths in the international E-road network.
"""

import collections
import heapq
import sys


class ERoadNetwork:
  """ Graph-based representation of the E-road network. """

  def __init__(self, include_water=True):
    """
    Initializes a path-finding object, optionally excluding water crossings.
    """
    pass  # TODO

  def shortest_path(self, src: str, dst: str) -> tuple[tuple, tuple, str] | None:
    """
    Returns several representations of the shortest path from `src` to `dst`.
    :param src: the starting location
    :param dst: the ending location
    :return: `None` if no path exists, or a tuple of three representations of the shortest path,
             as in the doctests below:

    >>> path_finder = ERoadNetwork()
    >>> import pprint
    >>> pprint.pprint(path_finder.shortest_path('Greenock, UK', 'Edinburgh, UK'))
    (('Greenock, UK', 'Glasgow, UK', 'Edinburgh, UK'),
     (('E05', ('Greenock, UK', 'Glasgow, UK')),
      ('E16', ('Glasgow, UK', 'Edinburgh, UK'))),
     'https://www.google.com/maps/dir/Greenock,+UK/Glasgow,+UK/Edinburgh,+UK')
    >>> pprint.pprint(path_finder.shortest_path('Stockholm, Sweden', 'Tallinn, Estonia'))
    (('Stockholm, Sweden', 'Tallinn, Estonia'),
     (('E20', ('Stockholm, Sweden', 'Tallinn, Estonia')),),
     'https://www.google.com/maps/dir/Stockholm,+Sweden/Tallinn,+Estonia')
    >>> land_only = ERoadNetwork(include_water=False)
    >>> pprint.pprint(land_only.shortest_path('Stockholm, Sweden', 'Tallinn, Estonia'))
    (('Stockholm, Sweden',
      'Sundsvall, Sweden',
      'Umeå, Sweden',
      'Luleå, Sweden',
      'Haparanda, Sweden',
      'Tornio, Finland',
      'Kemi, Finland',
      'Oulu, Finland',
      'Jyväskylä, Finland',
      'Lahti, Finland',
      'Helsinki, Finland',
      'Vaalimaa, Finland',
      'Sankt-Peterburg, Russia',
      'Tallinn, Estonia'),
     (('E04',
       ('Stockholm, Sweden',
        'Sundsvall, Sweden',
        'Umeå, Sweden',
        'Luleå, Sweden',
        'Haparanda, Sweden',
        'Tornio, Finland',
        'Kemi, Finland')),
      ('E75',
       ('Kemi, Finland',
        'Oulu, Finland',
        'Jyväskylä, Finland',
        'Lahti, Finland',
        'Helsinki, Finland')),
      ('E18',
       ('Helsinki, Finland', 'Vaalimaa, Finland', 'Sankt-Peterburg, Russia')),
      ('E20', ('Sankt-Peterburg, Russia', 'Tallinn, Estonia'))),
     'https://www.google.com/maps/dir/Stockholm,+Sweden/Sundsvall,+Sweden/Umeå,+Sweden/Luleå,+Sweden/Haparanda,+Sweden/Tornio,+Finland/Kemi,+Finland/Oulu,+Finland/Jyväskylä,+Finland/Lahti,+Finland/Helsinki,+Finland/Vaalimaa,+Finland/Sankt-Peterburg,+Russia/Tallinn,+Estonia')
    """
    pass  # TODO