fork(1) download
copy 
  1. # cook your dish here
  2. import sys
  3.  
  4. class Dijkstra:
  5.  
  6.     def __init__(self, vertices):
  7.         # from 1 to v
  8.         self.V = (vertices + 1)
  9.         self.graph = [[0 for row in range(self.V)] for j in range(self.V)]
  10.         # print(len(self.graph), len(self.graph[0]))
  11.  
  12.     def add_edge(self, src, dest, weight):
  13.         # directed graph
  14.         self.graph[src][dest] = weight
  15.  
  16.     def minimum_distance(self, dist, visited):
  17.         min_dist = sys.maxsize
  18.         min_idx = None
  19.  
  20.         for v in range(1, len(dist)):
  21.             if dist[v] < min_dist and visited[v] != True:
  22.                 min_dist = dist[v]
  23.                 min_idx = v
  24.         # print(min_idx)
  25.         return min_idx
  26.  
  27.     def shortest_path(self, src):
  28.         dist = [sys.maxsize] * self.V
  29.         visited = [False] * self.V
  30.  
  31.         dist[src] = 0
  32.  
  33.         for _ in range(1, self.V):
  34.             # find minimum distance verte which is not visited yet
  35.             u = self.minimum_distance(dist, visited)
  36.             visited[u] = True
  37.  
  38.             for v in range(1, self.V):
  39.                 if self.graph[u][v] > 0 and visited[v] != True:
  40.                     if self.graph[u][v] + dist[u] < dist[v]:
  41.                         dist[v] = self.graph[u][v] + dist[u]
  42.  
  43.         return dist
  44.  
  45.     def path_length(self, src, dest):
  46.         dist = self.shortest_path(src)
  47.         return dist[dest]
  48.  
  49.  
  50.  
  51. # main method
  52. t = int(input())
  53.  
  54. for _ in range(t):
  55.     V = None
  56.  
  57.     while not V:
  58.         try:
  59.             V = int(input())
  60.         except:
  61.             V = None
  62.             continue
  63.  
  64.  
  65.     city = dict()
  66.     g = Dijkstra(V)
  67.     # print(V)
  68.     for i in range(1, V+1):
  69.         cname = input()
  70.         city[cname] = i
  71.  
  72.         nedges = int(input())
  73.         for j in range(nedges):
  74.             v2, w = (int(x) for x in input().split())
  75.  
  76.             g.add_edge(i, v2, w)
  77.  
  78.  
  79.     n = int(input())
  80.     for j in range(0, n):
  81.         c1, c2 = (input().split())
  82.         print(g.path_length(city[c1], city[c2]))
  83.  
  84.  
  85.  
Success #stdin #stdout 0.03s 9232KB
comments (?)
stdin
copy 
1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa
stdout
copy 
3
2
https://ideone.com/FQU94J
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!