20182 골목 대장 호석 - 효율성 1

문제

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

20182번: 골목 대장 호석 - 효율성 1

 

접근

• 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