白駿1939|重量制限(BFS、二分ナビ)|パイソン
問題のソース:https://www.acmicpc.net/problem/1939
質問する
入力
問題の処理方法
この問題のヒントは,ブリッジの重量制限cが10億(10000000)であり,cpuが毎秒約1億個の数を演算できると仮定すると,時間複雑度がO(C)の場合,約10秒かかり,タイムアウトが発生することである.
したがって,この問題のようにNが非常に大きい場合には,二分探索やパラメータ測定の可能性を考慮すべきであり,時間的複雑度をO(log N)に低減できる.
パラメトリック検索とは?
決定問題(「YES」または「NO」)を最適化アルゴリズムに変換して解決する方法を二分探索を用いる.
この問題はパラメトリックメジャーによって
これは移動可能な重量の最低価格を探す問題です.
初期重量は(開始重量+最大重量)/2に設定します.
移動できる場合は「YES」を返します.
正解後、重量を増やし、より大きな重量が条件を満たすかどうかを探索します.
移動できない場合は「NO」を返します.
重量調整後、条件を満たすかどうかを探索します.
コード#コード#
import sys
from collections import deque
input = sys.stdin.readline
# n : 섬의 개수, m : 도로의 개수, graph = 섬들 간 의 연결 정보
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
island_1, island_2, weight = map(int, input().split())
graph[island_1].append((island_2, weight))
graph[island_2].append((island_1, weight))
# 문제에서 주어진 이동 가능한 무게의 최대값, 최솟값
min_weight = 1
max_weight = 1000000000
# 시작 도시와 도착 도시
start_island, end_island = map(int, input().split())
# BFS
# 이동 가능하면 큐에 넣고, 방문
# 큐에서 꺼낸 도시가 도착도시이면, 방문이 가능하다는 의미이므로 return True
# 이동이 가능한 도시에 대해서 BFS 탐색을 다 했는데 탐색이 종료되지 않았다면
# 종료도시는 무게 제한 때문에 갈 수 없다는 의미이므로 return False
def bfs(mid_weight):
queue = deque([start_island])
visited = set()
visited.add(start_island)
while queue:
island = queue.popleft()
if island == end_island:
return True
for next, weight in graph[island]:
if next not in visited and mid_weight <= weight:
visited.add(next)
queue.append(next)
return False
# 이분 탐색으로 이동 가능한 무게 탐색
result = min_weight
while min_weight <= max_weight:
mid = (min_weight + max_weight) // 2
if bfs(mid):
result = mid
min_weight = mid + 1
else:
max_weight = mid - 1
print(result)
Reference
この問題について(白駿1939|重量制限(BFS、二分ナビ)|パイソン), 我々は、より多くの情報をここで見つけました https://velog.io/@whddn0221/백준-1939-중량제한-BFS-이분탐색-파이썬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol