[테스트 케이스 추가] 백준 1504 특정한 최단 경로 python,파이썬

1. 문제

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

 

 

2. 풀이

다익스트라로 풀면 되고, 1->v1->v2->n, 1->v2->v1->n 그리고 연결이 안될 경우 INF인 경우를 세줘야 한다.

 

 

 

 

3. 구현

import sys
import heapq
import math

sys.stdin=open("input.txt")

v,e = map(int, sys.stdin.readline().split())

dist=[math.inf for i in range(v+2)]
gph=[[] for i in range(v+2)]
edges=[]

while e:
  e-=1
  a,b,c = map(int, sys.stdin.readline().split())
  gph[a].append((b,c))
  gph[b].append((a,c))

v1,v2 = map(int,sys.stdin.readline().split())
answer=0

def dijk(start, end):
  dist=[math.inf for i in range(v+2)]
  edges=[]
  dist[start]=0
  heapq.heappush(edges,(dist[start],start))
  while edges:
    cost, pos = heapq.heappop(edges)
    for p,c in gph[pos]:
      c+=cost
      if dist[p]>c:
        dist[p]=c
        heapq.heappush(edges,(c,p))
  return dist[end]

check = max(dijk(1,v1)+dijk(v1,v2)+dijk(v2,v), dijk(1,v2)+dijk(v2,v1)+dijk(v2,v))
answer = min(dijk(1,v1)+dijk(v1,v2)+dijk(v2,v), dijk(1,v2)+dijk(v2,v1)+dijk(v1,v))

if check==math.inf:
  print(-1)
else:
  print(answer)

 

 

 

4. 추가 테스트케이스

6 6
5 4 3 
5 3 6 
1 3 9 
1 4 1 
5 1 6 
3 4 4 
5 2

답 -1

(연결이 안된 경우)

 

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

답 13

(1->v2->v1->n이 더 작은 경우)