문제
https://www.acmicpc.net/problem/20182
접근
- 20168 골목 대장 호석 - 기능성 문제는 백트래킹으로 풀이했으나, 이 문제에서는 N과 M의 범위가 아래와 같으므로 시간초과 발생
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 500,000
- 솔직히 풀이 방법이 생각이 안나서 힌트를 참고해서 다익스트라를 써야한다는 것을 알았다.
- 그러나 문제는 출발지부터 목적지까지의 최단거리를 구하는 것이 아니라, 가지고 있는 비용 안에서 갈 수 있는 경로 안에 있는 수금액의 최댓값의 최솟값을 구하는 문제이므로 그냥 다익스트라로 못풀 것 같았다.
- 그러다가 어차피 답으로 출력할 수금액의 최댓값이 20으로 정해져있으므로, 파라메트릭 서치가 생각나서 수금액을 기준으로 이분탐색을 시도했다.
- 여기서 다익스트라는 경로 상 수금액의 최댓값이 주어진 mid값보다 작거나 같으면서 또한 그러한 경로가 가지고 있는 비용보다 작거나 같은지 확인하는 check 함수로 활용한다.
풀이
- 만약 주어진 mid 값보다 경로상의 수금액의 최댓값이 작거나 같으면서 또한 그러한 경로가 주어진 비용 안에서 갈 수 있는 경우라면 정답을 갱신하고 rt를 mid - 1로 바꾼다.
- 그렇지 않은 경우는 lt를 mid + 1로 바꾼다.
import heapq, sys
input = sys.stdin.readline
def dijkstra(mid):
q = []
heapq.heappush(q, (0, a))
dist = [-1] * (n + 1)
dist[a] = 0
while q:
cost, now = heapq.heappop(q)
if dist[now] != -1 and dist[now] < cost:
continue
for nxt, nxt_cost in graph[now]:
if nxt_cost > mid:
continue
nxt_cost += cost
if nxt_cost < dist[nxt] or dist[nxt] == -1:
dist[nxt] = nxt_cost
heapq.heappush(q, (nxt_cost, nxt))
if dist[b] != -1 and dist[b] <= c:
return True
return False
n, m, a, b, c = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
x, y, cost = map(int, input().split())
graph[x].append((y, cost))
graph[y].append((x, cost))
lt = 0
rt = 20
ans = -1
while lt <= rt:
mid = (lt + rt) // 2
if dijkstra(mid):
ans = mid
rt = mid - 1
else:
lt = mid + 1
print(ans)
20168 골목 대장 호석 - 기능성
def solve(now, max_val, sum):
global ans
if now == b:
if ans == -1 or max_val < ans:
ans = max_val
return
for nxt, cost in graph[now]:
if not check[nxt] and sum + cost <= c:
tmp = max(max_val, cost)
check[nxt] = True
solve(nxt, tmp, sum + cost)
check[nxt] = False
n, m, a, b, c = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
s, e, cost = map(int, input().split())
graph[s].append((e, cost))
graph[e].append((s, cost))
ans = -1
check = [False] * (n + 1)
check[a] = True
solve(a, 0, 0)
print(ans)
20183 골목 대장 호석 - 효율성 2
- lt와 rt 범위만 바꿔준 후 20182와 똑같은 코드 제출
- 시간초과 날 것 같았는데 통과했다.
lt = 0
rt = 10 ** 9
'Python > Coding Test' 카테고리의 다른 글
22869 징검다리 건너기 (small) (0) | 2022.02.27 |
---|---|
1863 스카이라인 쉬운거 (0) | 2022.02.26 |
21277 짠돌이 호석 (0) | 2022.02.24 |
10703 유성 (0) | 2022.02.24 |
13168 내일로 여행 (0) | 2022.02.23 |