boj 1238 : 파티

문제 주소: https://www.acmicpc.net/problem/1238

난이도: gold 4

1.문제설명

• N명의 학생이 X번 마을에 모여서 파티를 하려고한다.
• 이 마을에는 총 M개의 도로가 있고 도로는 단방향이다.(유향그래프)
• 모든 학생은 집에서 X에 갈수있고, X에서 집으로 돌아올 수 있을 때
• N명의 학생들 중 오고가는데 가장 오래걸리는 학생의 소요시간은?

2.문제해결 아이디어.

• 다익스트라 알고리즘을 통해 가는경우, 돌아오는 경우의 거리를 둘다 구한다.
• 학생별로 위 과정을 반복해서 가장 큰 값을 기록한다.

3.문제접근법

• 다익스트라 구현

def dijkstra(start):
    q = []
    distance = [INF] * (N + 1) #이부분이 함수 안에 구현됐다. 여러번 돌릴예정이기 떄문
    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[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance #distance를 return한다. 이를통해 누가 가장 많이 걸리는지 확인할 것

• 누가누가 가장 오래걸릴까?

ans = 0
for i in range(1,N+1):
    go = dijkstra(i) #i에서 시작했을 때 각 지점들까지의 최단거리를 담은 리스트
    back = dijkstra(X) # X(파티장소)에서 각 지점들까지의 최단거리를 담은 리스트
    ans = max(ans, go[X] + back[i]) #i에서 X까지 최단거리 + X에서 i까지 최단거리와 기존의 ans비교

4.특별히 참고할 사항

• heapq.headpush()가 없어진거같다..? 예전에 다익스트라 구현을할때 headpush로 해서 그대로 쓰니깐 오류가 났다.

5.코드구현

import heapq
import sys
input = sys.stdin.readline
INF = float(1e9)

N, M, X = map(int,input().split())
graph = [[]for i in range(N+1)]


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

def dijkstra(start):
    q = []
    distance = [INF] * (N + 1)
    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[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance

ans = 0
for i in range(1,N+1):
    go = dijkstra(i)
    back = dijkstra(X)
    ans = max(ans, go[X] + back[i])

print(ans)