[BOJ 1504]特定の最短経路(Python)
質問する
https://www.acmicpc.net/problem/1504
1番の頂点からn番の頂点に移動する場合は、任意に与えられた2つの頂点を通過する必要があります.
問題を解く
1番頂点からn番頂点に移動する場合、2つの頂点v 1,v 2をそれぞれ比較する必要があります.
この問題を解決するには、まずこの考えを考えなければならないようだ.💭
[1]1号➣v 1➣v 2➣n号
1번이 출발지이고, v1이 도착지일때 가장 짧은 경로 + v1이 출발지이고, v2가 도착지일때 가장 짧은 경로 + v2가 출발지이고, n번이 도착지일때 가장 짧은 경로[2]1号➣v 2➣v 1➣n号1번이 출발지이고, v2가 도착지일때 가장 짧은 경로 + v2가 출발지이고, v1이 도착지일때 가장 짧은 경로 + v1이 출발지이고, n번이 도착지일때 가장 짧은 경로2つの頂点を通過する場合は、上記のように分割し、より短いパス出力を選択すればよい.answer変数に格納されます.2-1.
answerがMAX_INTより大きい場合は、移動不可能なパスです.-1に戻ります.コード#コード#
import sys
import heapq
input = sys.stdin.readline
MAX_INT = sys.maxsize
def dijkstra(start):
distance = [MAX_INT for _ in range(n+1)]
q = [start] # [비용,시작점]
# 자기 자신의 거리 0으로 만들기
distance[start[1]] = 0
while q:
p = heapq.heappop(q)
cur_cost, cur_location = p[0], p[1]
# 현재 위치한 정점과 연결된 정점 Next 들 방문
for next_cost, next_location in graph[cur_location]:
# (연결된 정점으로 이동 비용) vs (현재 비용 + 이동 비용): 더 작은 값으로 할당 해줌
if distance[next_location] > cur_cost + next_cost:
distance[next_location] = cur_cost + next_cost
heapq.heappush(q,[distance[next_location],next_location])
return distance
n,e = map(int,input().rstrip().rsplit())
graph = [[] for _ in range(n+1)]
for _ in range(e):
a, b, c = map(int,input().rstrip().rsplit())
# graph[출발지] = [비용,도착지]
graph[a].append([c,b])
graph[b].append([c,a])
# 경유지 v1, v2
v1, v2 = map(int,input().rstrip().rsplit())
go = dijkstra([0,1])
v1go = dijkstra([0,v1])
v2go = dijkstra([0,v2])
answer = (min(go[v1]+v1go[v2]+v2go[n],go[v2]+v2go[v1]+v1go[n]))
if answer >= MAX_INT:
print(-1)
else:
print(answer)Reference
この問題について([BOJ 1504]特定の最短経路(Python)), 我々は、より多くの情報をここで見つけました https://velog.io/@uoayop/BOJ-1504-특정한-최단-경로Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol