BOJ 1939重量制限

7864 ワード
2021.05.20 テキストリンク
https://www.acmicpc.net/problem/1939
時間1秒、メモリ128 MB
input :
  • N, M(2≤N≤10,000)(1≤M≤100,000)
  • M行、A、B(1≦A、B≦N)、C(1≦C≦10000000)
    • 2つの異なる整数は、
  • 島の番号を表す.
    output :
  • 解答出力
    • 条件:
  • フルブリッジ双方向
    • 橋ごとに重量制限があるので、勝手に物を移動することはできません.重量制限を超えた貨物が橋を渡ると、橋が倒壊します.
  • 可動品重量の最高価格
    • どうせ注意しなければならないのは、私が今何キロ運んでいるのか、これは到着地点まで移動できるのかということです.
    では、bfsが終了した場所は現在の位置と終了点が同時にあるべきで、無視された部分はすでに訪問した場所であり、橋が今重さに耐えられない時である.
    そして最大重量を見つけなければならないので、この探索を利用して見つけなければなりません.重さは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)
    BOJ 10868最高価格
    geoserverベクトルサービス寸法【sdl】