[Python] 백준 11004 & 백준 10282

# 백준 11004번
# 수 N개 A1, A2, ... A_N이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 k번째 있는 수를 구하는 프로그램을 작성하시오

# 출력
# A를 정렬했을 때, 앞에서부터 k번째 있는 수를 출력한다.

# 문제 풀이 핵심 아이디어
# 데이터의 개수가 최대 5000000개 이므로 시간 복잡도 O(NlogN)의 정렬 알고리즘을 이용해야한다.
# 고급 정렬 알고리즘(병합 정렬, 퀵 정렬, 힙 정렬 등)을 이용하여 문제를 해결가능

def merge_sort(data):
    if len(data) <= 1:
        return data

    medium = int(len(data)) // 2
    left = merge_sort(data[:medium])
    right = merge_sort(data[medium:])
    merged = []
    left_point, right_point = 0, 0

    while len(left) > left_point and len(right) > right_point:
        if left[left_point] < right[right_point]:
            left.append(left[left_point])
            left_point += 1
        else:
            right.append(right[right_point])
            right_point += 1

        while len(left) > left_point:
            merged.append(left[left_point])
            left_point += 1

        while len(right) > right_point:
            merged.append(right[right_point])
            right_point += 1

        return merged


n, k = map(int, input().split(' '))
data = list(map(int, input().split(' ')))
merged = merge_sort(data)
print(merged[k - 1])# k번째 원소를 출력해야 하기때문에 k-1을 입력

 

#해킹 10282

import sys
import heapq

def dijkstra(graph, min_dist, start_node):
    queue = []
    heapq.heappush(queue, [0, start_node])
    min_dist[start_node] = 0
    while queue:
        dist, current = heapq.heappop(queue)
        if min_dist[current] < dist :
            continue
        for next, sec in graph[current]:
            cost = min_dist[current] + sec
            if cost < min_dist[next]:
                min_dist[next] = cost
                heapq.heappush(queue, [cost, next])


    return min_dist

t= int(input())
for _ in range(t):
    n, d, c = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(n+1)]
    min_dist = [1e9] * (n+1)
    for _ in range(d):
        a, b, s = map(int, sys.stdin.readline().split())
        graph[b].append([a,s])
    min_dist= dijkstra(graph, min_dist, c)

    answer = 0
    cnt = 0
    for i in min_dist:
        if i != 1e9:
            cnt += 1
            answer = max(answer, i)
    print(cnt, answer)