BOJ 1939 중량 제한
8045 단어 2021.05.202021.05.20
https://www.acmicpc.net/problem/1939
시간 1초, 메모리 128MB
input :
- N, M(2≤N≤10,000)(1≤M≤100,000)
- M개의 줄, A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)
- 섬의 번호를 나타내는 서로 다른 두 정수
output :
- 답을 출력
조건 :
- 모든 다리는 양방향
- 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.
- 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값
어차피 주목해야 할 부분은 내가 현재 몇 키로를 운송할 것인데 이게 도착지점까지 이동이 가능 하냐 이다.
그렇다면 bfs가 끝나는 지점은 현재 위치가 end지점과 같을 때 일 것이고, 무시하면 되는 부분은 이미 방문한 지점인것과, 다리가 현재 무게를 버티지 못할 때이다.
그리고 최대 무게를 찾아야 하니까 이를 이분 탐색을 이용해서 찾아야 한다. 중량의 무게가 10억까지 들어 올수 있어서 시간 복잡도가 힘들어 한다.
import sys
from collections import deque
def bfs():
check = [0] * (n + 1)
check[start] = 1
while q:
now = q.popleft()
if now == end:
return 1
for node, cost in graph[now]:
if check[node] == 1 or mid > cost:
continue
q.append(node)
check[node] = 1
return 0
n, m = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
a, b, c = map(int, sys.stdin.readline().split())
graph[a].append((b, c))
graph[b].append((a, c))
start, end = map(int, sys.stdin.readline().split())
left, right = 1, 1000000000
while left <= right:
q = deque([start])
mid = (left + right) // 2
if bfs() == 0:
right = mid - 1
else:
left = mid + 1
print(right)
Author And Source
이 문제에 관하여(BOJ 1939 중량 제한), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-1939-중량-제한저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)