백준 1238번 파티

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #그래프이론 #다익스트라

---

조건

시간 제한	메모리 제한
1 초	128 MB

---

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

---

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

---

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

---

예제 입출력 1

입력

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

출력

10

---

코드(파이썬)

from collections import defaultdict
import heapq
import sys


n, m, x = map(int, sys.stdin.readline().split())
towns = defaultdict(list)
towns_re = defaultdict(list)

for _ in range(m):
    s, e, w = map(int, sys.stdin.readline().split())
    
    towns[s].append((w, e))
    towns_re[e].append((-w, s))

d = [1010000] * (n+1)
d[x] = 0
queue = [[0, x]]
while queue:
    weight, town = heapq.heappop(queue)
    if d[town] >= weight:
        for next_weight, next_town in towns[town]:
            if next_weight+weight < d[next_town]:
                d[next_town] = next_weight + weight
                heapq.heappush(queue, (d[next_town], next_town))

d2 = [1010000] * (n+1)
d2[x] = 0
queue = [[0, x]]
while queue:
    weight, town = heapq.heappop(queue)
    weight = -weight
    
    if d2[town] >= weight:
        for next_weight, next_town in towns_re[town]:
            
            next_weight = -next_weight
            if next_weight+weight < d2[next_town]:
                d2[next_town] = next_weight + weight
                heapq.heappush(queue, (-d2[next_town], next_town))

print(max([d[i] + d2[i] for i in range(1, n+1)]))

---

특이사항

• 해결방법
  • x 도시에서 다른 도시까지의 최단경로를 다익스트라로 계산
  • 다른 도시에서 x 도시까지의 최단경로를 town_re를 통해 다익스트라를 반대로 활용해서 계산
• 내 코드(33,984KB, 664ms)에 비해 우수한 코드(바로가기, 33,932KB, 104ms)와 비교

  • import collections
    import heapq
    import sys
    
    def djikstra(lists,start):
        hq = []
        heapq.heappush(hq,[0,start])
        inf = int(1e9)
        res = [inf]*(n+1)
        res[start] = 0
        while hq:
            ex = heapq.heappop(hq)
            if ex[0] > res[ex[1]]:
                continue
            for price,go in lists[ex[1]]:
                cost = ex[0] + price
                if cost < res[go]:
                    res[go] = cost
                    heapq.heappush(hq,[cost,go])
        return res[1:]
    n,m,x = map(int,sys.stdin.readline().split())
    distance_x = [[] for _ in range(n+1)]
    distance_y = [[] for _ in range(n+1)]
    for i in range(m):
        a,b,c = map(int,sys.stdin.readline().split())
        distance_x[a].append([c,b])
        distance_y[b].append([c,a])
            
    go_x = djikstra(distance_x,x)
    go_home = djikstra(distance_y,x)
    print(max([x+y for x,y in zip(go_x,go_home)]))
    

  • 목적지 -> 모든 노드 다익스트라 적용
    • 기존: 도시간 거리에 - 연산 추가
    • 개선: 도시간 거리를 그대로 사용

---

참고문헌

-