fork download
copy 
  1. class Vertex:
  2.     def __init__(self, data):
  3.        self.ver = data
  4.        self.pre = None
  5.        self.d = 2147483647
  6.        self.adj = []
  7.  
  8. def parent(i):
  9.     return (i-1)//2
  10.  
  11. def left(i):
  12.     return i*2 + 1
  13.  
  14. def right(i):
  15.     return 2*i + 2
  16.  
  17.  
  18. def Build_Min_Heap(A):
  19.     heapsize = len(A)-1
  20.     for i in range(heapsize//2, -1, -1):
  21.         Min_Heapify(A, i)
  22.     return A
  23.  
  24. def Min_Heapify(A, i):
  25.     heapsize = len(A)-1
  26.     l = left(i)
  27.     r = right(i)
  28.     if l <= heapsize and A[l].d < A[i].d:
  29.         smallest = l
  30.     else:
  31.         smallest = i
  32.     if r<= heapsize and A[r].d < A[smallest].d:
  33.         smallest = r
  34.     if smallest != i:
  35.         temp = A[i]
  36.         A[i] = A[smallest]
  37.         A[smallest] = temp
  38.         Min_Heapify(A, smallest)
  39.  
  40. def Heap_Extract_Min(A):
  41.     heapsize = len(A)-1
  42.     if heapsize < 0:
  43.         return
  44.     min = A[0]
  45.     A[0] = A[heapsize]
  46.     del A[heapsize]
  47.     Min_Heapify(A,0)
  48.     return min
  49.  
  50. def Relax(u, v, w):#decrease-key #V가 그냥 노드 이름이고 클래스가 아님. 
  51.      if v.d > u.d + w:
  52.         v.d = u.d + w
  53.         v.pre = u
  54.  
  55. def DIJKSTRA(G):
  56.     G[0].d = 0
  57.     S = []
  58.     Q = Build_Min_Heap(G)
  59.     while Q:
  60.         u = Heap_Extract_Min(Q) #A다음에 E가 나옴. min-heap이 잘못된듯.
  61.         S.append(u)
  62.         for a in u.adj: #a는 인접노드 리스트
  63.             for i in range(len(Q)):
  64.                 if a[0] == Q[i].ver:
  65.                     Relax(u, Q[i], int(a[1]) )
  66.                     break
  67.             for i in range(len(S)):
  68.                 if a[0] == S[i].ver:
  69.                     Relax(u, S[i], int(a[1]) )
  70.                     break
  71.  
  72.             Min_Heapify(Q, 0) #a에 해당하는 class를 찾아줌->all[i]
  73.     return S
  74.  
  75. def Print_Shortest_Path(G):
  76.     for a in node:
  77.         for i in range(len(G)):
  78.             if a == G[i].ver:
  79.                 print(G[i].d)
  80.                 break
  81.  
  82. node = list() 
  83. node = (input().split(',')) #노드 받기
  84. n = int(input()) #edge 수 받기. 
  85.  
  86. all = list()
  87. for a in node:
  88.     all.append(Vertex(a))
  89.  
  90. VERS = all[:]
  91.  
  92. for i in range(n):
  93.     edge = []
  94.     edge = input().split(',')
  95.     for a in node:
  96.         if a == edge[0]:
  97.             j = node.index(a)
  98.             all[j].adj.append([edge[1], edge[2]])
  99.             break
  100.  
  101. result = DIJKSTRA(all)
  102. Print_Shortest_Path(result)
Success #stdin #stdout 0.03s 9896KB
comments (?)
stdin
copy 
A,B,C,D,E,F,G,H,I,J,K,L,M,N
98
A,G,7
A,H,4
A,I,6
A,J,1
A,L,3
A,N,7
B,F,1
B,H,6
B,I,3
B,J,5
B,L,2
C,A,7
C,B,6
C,D,4
C,E,1
C,F,3
C,J,3
C,K,2
C,L,7
C,M,3
C,N,4
D,B,7
D,E,1
D,F,7
D,I,5
D,J,6
D,K,2
D,L,2
D,M,1
D,N,5
E,B,7
E,C,3
E,D,5
E,I,1
E,J,5
E,M,1
F,A,2
F,L,2
F,N,2
G,A,4
G,C,7
G,I,7
G,J,7
G,K,4
G,L,4
G,M,2
G,N,2
H,B,7
H,D,2
H,E,2
H,G,2
H,J,4
H,L,5
H,M,7
H,N,6
I,D,2
I,E,6
I,F,1
I,J,4
J,A,6
J,B,7
J,D,3
J,F,6
J,I,4
J,L,1
J,M,6
K,A,7
K,B,4
K,C,3
K,E,6
K,F,5
K,H,6
K,I,7
K,J,4
K,N,4
L,A,7
L,C,2
L,D,5
L,F,1
L,I,6
L,J,7
L,K,2
L,M,7
M,A,5
M,B,6
M,C,3
M,E,1
M,F,5
M,G,7
M,H,7
M,I,3
M,J,7
M,N,3
N,A,3
N,H,7
N,I,6
N,J,1
N,M,1
stdout
copy 
0
8
5
4
5
4
6
4
5
1
5
2
5
6
https://ideone.com/zt4qOS
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
public

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!