[백준 15709] 정기검진
1. 문제 설명
2. 문제 분석
'다리'를 시작점으로 집과 병원을 이어줄 수 있다. 어느 다리에서 출발했을 때 최소 거리가 걸리는지 모르기 때문에 (그리고 집과 병원의 위치에 따라서 달라질 수 있기 때문에) 모든 다리를 시작점으로 사용해 다익스트라 알고리즘을 사용할 수 있다.
- (집+병원+다리)가 모두 노드로 사용된다는 점에서 다리-다리를 잇는 간선도 존재한다는 점에 주의.
3. 나의 풀이
import sys
import heapq
from collections import deque
INF = sys.maxsize
n, m, b, k, q = map(int, sys.stdin.readline().rstrip().split())
# 총 (n+m+b) 개 노드, k 개 간선
nodes = [[] for _ in range(n+m+b+1)]
distances = [[INF for _ in range(n+m+b+1)] for _ in range(b+1)]
# 다리 별로 다익스트라를 만들기 위한 distances
for _ in range(k):
node1, node2, cost = map(int, sys.stdin.readline().rstrip().split())
nodes[node1].append([node2, cost])
nodes[node2].append([node1, cost])
def Dijkstra(start):
pq = []
heapq.heappush(pq, [0, start])
distances[start-n-m][start] = 0
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[start-n-m][cur_node] != cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if distances[start-n-m][next_node] > next_cost + cur_cost:
distances[start-n-m][next_node] = next_cost + cur_cost
heapq.heappush(pq, [next_cost + cur_cost, next_node])
for bridge in range(n+m+1, n+m+b+1):
Dijkstra(bridge)
# 각 다리에 대해 다익스트라 알고리즘
for _ in range(q):
s, e = map(int, sys.stdin.readline().rstrip().split())
answer = INF
for bridge in range(n+m+1, n+m+b+1):
answer = min(answer, distances[bridge-n-m][s] + distances[bridge-n-m][e])
# 특정 다리를 시작점으로 사용했을 때 해당 다리 -> s, 해당 다리 -> e의 합이 s -> e까지 걸리는 거리
if answer == INF: print(-1)
else: print(answer)
Author And Source
이 문제에 관하여([백준 15709] 정기검진), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-15709-정기검진
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
'다리'를 시작점으로 집과 병원을 이어줄 수 있다. 어느 다리에서 출발했을 때 최소 거리가 걸리는지 모르기 때문에 (그리고 집과 병원의 위치에 따라서 달라질 수 있기 때문에) 모든 다리를 시작점으로 사용해 다익스트라 알고리즘을 사용할 수 있다.
- (집+병원+다리)가 모두 노드로 사용된다는 점에서 다리-다리를 잇는 간선도 존재한다는 점에 주의.
3. 나의 풀이
import sys
import heapq
from collections import deque
INF = sys.maxsize
n, m, b, k, q = map(int, sys.stdin.readline().rstrip().split())
# 총 (n+m+b) 개 노드, k 개 간선
nodes = [[] for _ in range(n+m+b+1)]
distances = [[INF for _ in range(n+m+b+1)] for _ in range(b+1)]
# 다리 별로 다익스트라를 만들기 위한 distances
for _ in range(k):
node1, node2, cost = map(int, sys.stdin.readline().rstrip().split())
nodes[node1].append([node2, cost])
nodes[node2].append([node1, cost])
def Dijkstra(start):
pq = []
heapq.heappush(pq, [0, start])
distances[start-n-m][start] = 0
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[start-n-m][cur_node] != cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if distances[start-n-m][next_node] > next_cost + cur_cost:
distances[start-n-m][next_node] = next_cost + cur_cost
heapq.heappush(pq, [next_cost + cur_cost, next_node])
for bridge in range(n+m+1, n+m+b+1):
Dijkstra(bridge)
# 각 다리에 대해 다익스트라 알고리즘
for _ in range(q):
s, e = map(int, sys.stdin.readline().rstrip().split())
answer = INF
for bridge in range(n+m+1, n+m+b+1):
answer = min(answer, distances[bridge-n-m][s] + distances[bridge-n-m][e])
# 특정 다리를 시작점으로 사용했을 때 해당 다리 -> s, 해당 다리 -> e의 합이 s -> e까지 걸리는 거리
if answer == INF: print(-1)
else: print(answer)
Author And Source
이 문제에 관하여([백준 15709] 정기검진), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-15709-정기검진
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
import heapq
from collections import deque
INF = sys.maxsize
n, m, b, k, q = map(int, sys.stdin.readline().rstrip().split())
# 총 (n+m+b) 개 노드, k 개 간선
nodes = [[] for _ in range(n+m+b+1)]
distances = [[INF for _ in range(n+m+b+1)] for _ in range(b+1)]
# 다리 별로 다익스트라를 만들기 위한 distances
for _ in range(k):
node1, node2, cost = map(int, sys.stdin.readline().rstrip().split())
nodes[node1].append([node2, cost])
nodes[node2].append([node1, cost])
def Dijkstra(start):
pq = []
heapq.heappush(pq, [0, start])
distances[start-n-m][start] = 0
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[start-n-m][cur_node] != cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if distances[start-n-m][next_node] > next_cost + cur_cost:
distances[start-n-m][next_node] = next_cost + cur_cost
heapq.heappush(pq, [next_cost + cur_cost, next_node])
for bridge in range(n+m+1, n+m+b+1):
Dijkstra(bridge)
# 각 다리에 대해 다익스트라 알고리즘
for _ in range(q):
s, e = map(int, sys.stdin.readline().rstrip().split())
answer = INF
for bridge in range(n+m+1, n+m+b+1):
answer = min(answer, distances[bridge-n-m][s] + distances[bridge-n-m][e])
# 특정 다리를 시작점으로 사용했을 때 해당 다리 -> s, 해당 다리 -> e의 합이 s -> e까지 걸리는 거리
if answer == INF: print(-1)
else: print(answer)
Author And Source
이 문제에 관하여([백준 15709] 정기검진), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@j_aion/백준-15709-정기검진저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)