[테스트케이스 추가] 백준 15422번: Bumped! (python, 파이썬)

1. 문제

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

15422번: Bumped!

Peter는 최근에 개최 된 ACM ICPC World Finals에서 돌아와서 돌아 오는 항공편이 초과 예약되어 두 목적지 사이의 무료 비행에 대한 바우처를 받았습니다.

그는 이미 내년 여행을 계획하고 있습니다. 그는 필요한 경우 자동차로 여행 할 계획이지만 여행의 한쪽 다리에 무료 항공권을 사용할 수 있습니다. 그는 계획에 도움을 요청했습니다.

그는 도로로 연결된 도시 네트워크, 도시 쌍 사이를 여행 할 때 가스를 구입하는 데 드는 비용, 일부 도시 간 사용 가능한 항공편 목록을 제공 할 수 있습니다. 피터가 고향에서 내년 목적지로 이동하는 데 필요한 최소 금액을 찾아 도와주세요!

 

입력은 단일 테스트 케이스로 구성됩니다. 첫 번째 줄에는 5 개의 공백으로 구분 된 정수 n, m, f, s 및 t가 나열되며, 이는 도시 수 n (0 <n ≤ 50,000), 도로 수 m (0 ≤ m ≤ 150,000), 항공편 수 f (0 ≤ f ≤ 1,000), Peter의 여정이 시작되는 도시의 s (0 ≤ s <n) 및 Peter가 시도하려는 도시의 수 t (0 ≤ t <n) 여행. (도시 번호는 0에서 n-1까지입니다.)

첫 번째 줄 다음에는 각각 하나의 도로를 설명하는 m 개의 줄이 이어집니다. 도로 설명에는 3 개의 공백으로 구분 된 정수 i, j 및 c (0 ≤ i, j <n, i ≠ j 및 0 <c ≤ 50,000)가 포함되어 있습니다. 이는 c 센트 비용이 드는 도시 i와 j를 연결하는 도로가 있음을 나타냅니다. 여행. 도로는 동일한 비용으로 양방향으로 사용할 수 있습니다. 모든 도로 설명은 고유합니다. 다음의 각 f 행에는 사용 가능한 항공편에 대한 설명이 포함되어 있으며, 두 개의 공백으로 구분 된 정수 u 및 v (0 ≤ u, v <n, u ≠ v)로 구성되어 도시 u에서 도시 v까지의 비행이 가능함을 나타냅니다 ( 다른 곳에 나열되지 않는 한 v에서 u까지는 아닙니다). 모든 비행 설명은 고유합니다.

 

피터가 고향에서 대회까지 가기 위해 지출해야하는 최소 센트를 최대 한 번의 항공편으로 출력합니다. 베드로가 목적지에 도달 할 수있는 경로가 있다고 가정 할 수 있습니다.

 

 

 

2. 풀이

1) 다익스트라를 중간에 끊는다

( s->비행기 출발점 + 비행기도착점->t ) 과  일반도로로 가는 것 중 더 작은 것을 선택한다.

2) 끊지 않고 도로로 가는 경우. 즉 그냥 dijkstra(s,t)를 구한다.

 

두 가지 중 작은 것을 return 한다.

 

- 런타임에러가 나면 sys.setrecursionlimit(10**8)한다.

- 나는 road와 flight 둘 다 그래프를 만들어서 메모리초과도 났었다. flight는 들어오는 대로 처리했더니 해결됐다. 다만 flight가 0인 경우 flight 비교문을 돌지 않을 수 있어서 이경우를 유의한다.

 

 

3. 구현

import sys
import heapq
import math
sys.setrecursionlimit(10**8)

# sys.stdin = open('input.txt')
#도시, 도로, 항공편 갯수 , 시작점, 여행하려는 도시 갯수
n, m, f, s, t = map(int, sys.stdin.readline().split()) 

gph=[[] for _ in range(n+2)]

while m:
  m-=1
  i,j,c = map(int, sys.stdin.readline().split())
  gph[i].append((j,c))
  gph[j].append((i,c))

def dijk(node):
  dist=[ math.inf for _ in range(n+2)]
  edges=[]

  dist[node]=0
  heapq.heappush(edges, (dist[node], node))
  
  while edges:
    cost, pos = heapq.heappop(edges)
    if dist[pos]<cost:
      continue
    for p, c in gph[pos]:
      c+=cost
      if dist[p]>c:
        dist[p]=c
        heapq.heappush(edges, (c,p))
  return dist

ans=math.inf
# airplane
while f:
  f-=1
  u,v = map(int, sys.stdin.readline().split())
  ans = min(dijk(s)[u]+dijk(v)[t], ans)

# by road
ans = min(ans,dijk(s)[t])

print(ans)

 

 

 

4. 테스트케이스 추가

여기에서 대회 TC를 확인할 수 있다.

 

 

input.txt

0.88MB

답:

2499950000

 

2 1 0 0 1
0 1 10

답:

10

 

input.txt

2.50MB

답: 

16917

 

input.txt

1.40MB

답:

49999

 

2 1 1 1 0
0 1 10
0 1

답:

10