백준 1238번 <파티>

백준 알고리즘 1238번

https://www.acmicpc.net/problem/1238

1238번: 파티

---

1238번

입력으로 첫 줄에 학생의 수 N과 도로의 수 M, 파티가 열리는 마을의 번호 X가 주어진다.

그 다음에 M개의 줄에 도로의 정보가 주어진다. (이때 "시작점 끝점 소요시간"으로 들어온다. 이는 시작점에서 끝점으로 가는데 소요시간이 든다는 의미다.)

 

출력으로 N명의 학생들이 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

---

문제 해결

이 문제도 18352번 문제와 같이 다익스트라 알고리즘을 사용하여 해결하면 된다.

다익스트라 알고리즘은 한 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘이다.

 

for문을 이용하여 각 마을에서 다른 모든 마을로 가는 최소 시간을 구한다.

-> 각 학생들의 마을에서 마을 X로 가는 최소 시간을 구했고

-> 마을 X에서 각 학생들의 마을로 가는 최소 시간을 구했다.

 

따라서 각 학생들의 마을에서 마을 X로 가는 최소 시간과 마을 X에서 각 학생들의 마을로 가는 최소 시간을 더한 값이 가장 큰 값을 출력하면 된다.

---

코드

import heapq
INF = int(1e9)

def main():
    n, m, k = map(int, input().split())
    graph = [[]for _ in range(n+1)]

    for i in range(m):
        a, b, c = map(int, input().split())
        graph[a].append((c, b))

    temp = [[] for _ in range(n+1)]
    for i in range(1, n+1):
        temp[i] = dijkstra(i, graph, n)

    max = 0
    for i in range(1, n+1):
        sum = temp[i][k] + temp[k][i]
        if max < sum:
            max = sum
    print(max)


def dijkstra(start, graph, n):
    distance = [INF] * (n+1)

    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[0]
            if cost < distance[i[1]]:
                distance[i[1]] = cost
                heapq.heappush(q, (cost, i[1]))
    return distance

main()

---

결과

---