[백준] 군사 이동

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

11085번: 군사 이동

 

경로에 존재하는 가장 넓은 너비를 구하는 것이 목적인 문제입니다. 지나갈 수 있는 최소 너비를 지정해주고 이보다 큰 간선만을 택하면서 다익스트라를 수행한 다음 목적지에 도달할 수 있는지를 체크하면  풀 수 있습니다. 

 

# 문제링크: https://www.acmicpc.net/problem/11085
import sys, os, heapq
from collections import defaultdict

# sys.stdin = open(os.curdir + "\\input.txt", "r")
input = sys.stdin.readline
INT_MAX = sys.maxsize

# p개의 노드, w개의 간선
p, w = tuple(map(int, input().split()))

# c: 시작점, v: 도착점
c, v = tuple(map(int, input().split()))

graph = defaultdict(list)

# 그래프 구성
for _ in range(w):
    start, end, weight = tuple(map(int, input().split()))
    graph[start].append((end, weight))
    graph[end].append((start, weight))

def dijkstra(start, end, min_weight):
    dist = [INT_MAX] * p
    dist[start] = 0

    q = [(0, start)]

    while q:
        cur_dist, cur_node = heapq.heappop(q)

        for next_node, next_weight in graph[cur_node]:
            # 최소 간선의 가중치보다 큰 간선에 대해서만 다익스트라를 진행
            if next_weight >= min_weight:
                next_dist = cur_dist + next_weight

                if next_dist < dist[next_node]:
                    dist[next_node] = next_dist

                    heapq.heappush(q, (next_dist, next_node))

    return True if dist[end] != INT_MAX else False

answer = 0

# 지나갈 수 있는 최소 간선의 가중치를 정해두고 이보다 큰 간선만 택하여 경로를 찾을 수 있는지 확인
for min_weight in range(1000, -1, -1):
    if dijkstra(c, v, min_weight):
        answer = min_weight
        break

print(answer)