[Python] 백준 1916 & 백준 2309

# 백준 1916

import heapq
import sys

input = sys.stdin.readline
n= int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])

start, end = map(int, input().split())


def dijkstra(start, end):
    queue = []
    min_dist = [1e9] * (n + 1)
    heapq.heappush(queue, [0, start])
    min_dist[start] = 0
    while queue:
        current_dist, current_node = heapq.heappop(queue)
        if min_dist[current_node] > current_dist:
            min_dist[current_node] = current_dist
        if current_node == end:
            return min_dist[end]
        for next_node, weight in graph[current_node]:
            cost= min_dist[current_node] + weight
            if cost < min_dist[next_node]:
                min_dist[next_node] = cost
                heapq.heappush(queue, [cost, next_node])

print(dijkstra(start,end))

 

# 백준 2309 

import sys

input = sys.stdin.readline

heights = []
for _ in range(9):
    heights.append(int(input()))

possible = []
def dfs(depth):
    if depth == 7 :
        if sum(possible) == 100:
            for i in sorted(possible):
                print(i)
            exit()
        else:
            return
    for i in range(depth, 9):
        possible.append(heights[i])
        dfs(depth+1)
        possible.pop()

dfs(0)