백준 5551번 쇼핑몰

문제

상근이가 지배하는 나라에는 도시가 N개 있고, 도시는 M개의 양방향 도로로 연결되어 있다. 이 중 K개 도시에는 쇼핑몰이 있고, 국민은 도로를 통해서 쇼핑몰이 있는 마을로 가고, 쇼핑을 한다.

쇼핑몰이 멀리 떨어져 있는 사람은 쇼핑몰로 가기 위해 긴 시간 운전을 해야 한다. 상근이는 실정을 파악하기 위해서 쇼핑몰과 집의 최단 거리가 집의 위치에 따라서 어떻게 달라지는지 구하기로 한다. 집은 도시에 있을 수도 있고, 도로 위에 있을 수도 있다.

도로의 정보와 쇼핑몰이 있는 도시가 주어졌을 때, 쇼핑몰이 있는 도시와 가장 먼 거리에 있는 집까지의 거리를 구하는 프로그램을 작성하시오. 도시 속을 이동하는데 걸리는 시간은 0이다. 또, 사람들은 항상 최단 경로를 이용한다.

입력

첫째 줄에 도시의 수 N, 도로의 수 M, 쇼핑몰이 있는 도시의 수 K가 주어진다. 도시는 1번부터 N번까지 번호가 매겨져 있다. (2 ≤ N ≤ 3000, 1 ≤ M ≤ 105, 1 ≤ K ≤ N)

다음 M개 줄에는 도로의 정보 a, b, l이 주어진다. a와 b를 잇는 도로의 길이가 l(1 ≤ l ≤ 1000)임을 의미하며, a와 b가 같은 경우는 없다. 두 도시 p와 q에 대해서, 두 도시를 잇는 도로는 2개 이상 존재하지 않는다. 항상 도로를 이용해서 모든 도시로 이동할 수 있다.

다음 K개 줄에는 쇼핑몰이 있는 도시의 번호가 주어진다. 한 도시에 쇼핑몰이 여러 개 있을 수는 없다.

출력

쇼핑몰이 있는 곳에서 가장 멀리 떨어져 있는 집과의 거리(쇼핑몰과 집의 최단 거리의 최솟값)를 소수점 첫째자리에서 반올림해서 출력한다.

 

2. 코드

import sys
from heapq import heappop, heappush

input = sys.stdin.readline
INF = sys.maxsize

def dijstra(start):
    queue = []
    heappush(queue, (0, start))

    dis[start] = 0

    while queue:
        dist, now = heappop(queue)

        if dis[now] < dist:
            continue
        for i in maps[now]:
            cost = dist + i[1]

            if cost < dis[i[0]]:
                dis[i[0]] = cost
                heappush(queue, (cost, i[0]))
n, m, k = map(int, input().split())

maps = [[] for _ in range(n + 1)]
dis = [INF] * (n + 1)
edge = []
for _ in range(m):
    a, b, c = map(int, input().split())
    maps[a].append((b, c))
    maps[b].append((a, c))
    edge.append((a, b, c))

shopping = [int(input()) for _ in range(k)]
ans = 0
for a in shopping:
    dijstra(a)

for a, b, c in edge:
    ans = max(ans, (dis[a] + dis[b] + c + 1) // 2)
print(ans)

 

3. 문제 해결법

1. 편의점 노드를 기준으로 다익스트라를 돌려 최단 거리 값을 갱신한다.

2. 집의 위치는 노드 가 될수 있고 도로 안에도 가능 하다.

3. u의 거리 값과 v의 거리 값 그리고 가중치 c + 1 값을 2로 나누었을때 편의점 과 집의 거리가 최대로 된다.