[python]1504번 🔥특정한 최단 경로

반드시 지나야할 두 점을 체크포인트처럼 부분적으로 최단거리들을 구하고 모두 합 칠 생각을 못했다.

 

두 점을 지날때 순서는 바뀔 수 있으므로 두 경우 모두 구해야했다.

1 - 첫번째 중간지점 - 두번째 중간지점 - 끝

1 - 두번째 중간지점 - 첫번째 중간지점 - 끝

 

import sys
from heapq import heappush,heappop
input = sys.stdin.readline
node,edge = map(int,input().split())
graph = [[]for i in range(node+1)]
def dxt(start,end):
    cost = [1e9 for i in range(node+1)]
    cost[start] = 0
    que = [[0,start]]
    while que:
        cur = heappop(que)
        for idx,val in graph[cur[1]]:
            if cost[idx]>cost[cur[1]]+val:
                cost[idx] = cost[cur[1]]+val
                heappush(que,(cost[idx],idx))
    return cost[end]
for i in range(edge):
    fst,scd,thd = map(int,input().split())
    graph[fst].append((scd,thd))
    graph[scd].append((fst,thd))
ess1,ess2 = map(int,input().split())
case1 = dxt(1,ess1)+dxt(ess1,ess2)+dxt(ess2,node)   #두 경우 모두 구하기
case2 = dxt(1,ess2)+dxt(ess2,ess1)+dxt(ess1,node)
if case1>=1e9 and case2>=1e9:        # 두경우 모두 방법이 없을 때
    print(-1)
else:
    print(case1 if case1<=case2 else case2)

그러나 함수 호출 빈도수를 더 줄일 수 있어 시간이 더 줄어드는 방법이 있다.

위에 방법은 시작,끝을 인자로 받아 그에 맞는 목적지까지의 거리값을 반환하였기에, 구간값을 구할 때마다 함수 호출이 필요했다.

 

그러나 1번, 중간지점1, 중간지점2들의 각각의 거리배열들을 알게 되면 배열인덱싱을 통해 값을 더해서 비교할 수 있다.

따라서 함수를 3번만 호출가능해 시간이 덜 걸린다.

 

import sys
from heapq import heappush,heappop
input = sys.stdin.readline
def dij(start):
    distance = [1e9 for i in range(node+1)]
    distance[start] = 0
    que = [(0,start)]
    while que:
        cur = heappop(que)
        for nextx,nextlen in graph[cur[1]]:
            if distance[nextx]>nextlen+cur[0]:
                distance[nextx]=nextlen+cur[0]
                heappush(que,(distance[nextx],nextx))
    return distance #그냥 거리값이 들어있는 배열을 반환하기
node,edge = map(int,input().split())
graph = [[] for i in range(node+1)]
for i in range(edge):
    fst,scd,thd = map(int,input().split())
    graph[fst].append((scd,thd))
    graph[scd].append((fst,thd))
ess1,ess2 = map(int,input().split())
start_dis = dij(1) #1에서 부터 시작하는 배열
ess1_dis = dij(ess1) #중간지점 1번 부터 시작하는 배열
ess2_dis = dij(ess2) #중간지점 2번 부터 시작하는 배열
if start_dis[ess1]+ess1_dis[ess2]+ess2_dis[node] >=1e9 and start_dis[ess2]+ess2_dis[ess1]+ess1_dis[node]>=1e9:
    print(-1) #목적지까지 도달 할 수 없을때
else: #배열을 인덱싱해서 값들만 더해서 더 작은 값을 출력
    print(min(start_dis[ess1]+ess1_dis[ess2]+ess2_dis[node],start_dis[ess2]+ess2_dis[ess1]+ess1_dis[node]))