11779백준

다익스트라

 
from sys import stdin
 
N = int(stdin.readline())
L = int(stdin.readline())
INF = int(1e9)
 
graph = {n : [] for n in range(N+1)}
visit = [False for i in range(N+1)]
vertex = [INF for i in range(N+1)]
track = [-1 for i in range(N+1)]
 
for _ in range(L):
  s, e, cost = map(int, stdin.readline().split(" "))
  graph[s].append([e,cost])
 
start, end = map(int, stdin.readline().split(" "))
 
def retNextNode(visit, vertex):
  global N
  mincost = INF
  v = 0
  for i in range(1,N+1):
    if visit[i] == False and mincost > vertex[i]:
      mincost = vertex[i]
      v = i
  return v
 
 
def shortcut(s,e):
  global N, L
  
  visit[s] = True
  vertex[s] = 0
  
  for v in graph[s]:
    if 0+  v[1] < vertex[v[0]]:
      vertex[v[0]] = v[1]
  
  for j in range(1,N):
    nextNode = retNextNode(visit,vertex)
    visit[nextNode] = True
    for nn in graph[nextNode]:
      if vertex[nextNode] + nn[1] <= vertex[nn[0]]:
        vertex[nn[0]] = vertex[nextNode] + nn[1]
        track[nn[0]] = nextNode
  return track  
 
shortcut(start,end)
 
trace = [end]
pointer =end
while True:
  if track[pointer] == -1 or pointer ==start:
    break
  trace.append(track[pointer])
  pointer = track[pointer]
trace.append(start)
print(vertex[end])
print(len(trace))
trace.reverse()
print(*trace, sep=" ")