K番目の数

ソース:白駿#1939
タイムアウトメモリ制限1秒128 MB

質問する

N(2≦N≦10000)個の島からなる国がある.その中のいくつかの島の間には橋があり、開通することができます.
永植重工業は二つの島に工場を建てて物品を生産する.物を生産する時、工場から他の工場に生産中の物を運ぶことがよくあります.しかし、どの橋にも重量制限があるので、勝手に荷物を運ぶことはできません.重量制限を超えた貨物が橋を渡ると、橋が倒壊します.
1回の移動で移動可能な物品の重量の最低価格を求めるプログラムを作成します.

入力

第1行はN,M(1≦M≦100000)を与える.次のM行は、3つの整数A,B(1≦A,B≦N),C(1≦C≦10000000)を与え、ブリッジに関する情報を表す.これは、A号島とB号島の間に重量制限Cの橋があることを意味する.2つの島の間には複数の橋があるかもしれませんが、それぞれの橋は双方向です.最後の行には、工場が存在する島の番号を示す2つの異なる整数が表示されます.工場がある2つの島を接続するパスには、常に存在するデータのみが入力されます.

しゅつりょく

最初の行に答えを印刷します.

I/O例

入力例1

3 3
1 2 2
3 1 3
2 3 2
1 3

サンプル出力1

3

に答える

の意見を打診

は最初はリンクリストで解けていたが、タイムアウトした.

の理由は、リンクリストを探索するbfs関数で受信するプロセスに時間がかかったようだ.(不確定、再検査が必要)

したがって、

は、隣接リストをリスト形式で整理して解く.

説明する

wを入力すると、最大値を持つwがmax_weightとして記録される.

したがって、1と

の中間中間中間者midを設定し、相応の重量以上を越えるだけで目的地に着くことができる.

の目的地に到着できれば、その時のmid値を答えに記入します.

、左側の値をmid+1に更新して、さらにナビゲートします.

目的地に到達できない場合は、さらに重量を低減し、正確な値をmid−1に更新してさらに探索する必要がある.

python code

# 백준 1939번
from sys import stdin
import sys
from collections import deque
sys.setrecursionlimit(10**6)

class Node:
    def __init__(self, vertex, weight):
        self.vertex = vertex
        self.weight = weight
        self.next = None

class Graph:
    def __init__(self, size):
        self.adjList = [None] * (size+1) # 0은 없으므로
        self.adjList2 = [[] for _ in range(size+1)]
        self.size = size+1

    def insertEdge(self, v1, v2, w):    # linked list
        newNode = Node(v2, w)
        newNode.next = self.adjList[v1]
        self.adjList[v1] = newNode

        newNode = Node(v1, w)
        newNode.next = self.adjList[v2]
        self.adjList[v2] = newNode

    def bfs(self, start, dest, box_weight):
        visited = [False] * (self.size+1)
        queue = deque([start])
        visited[start] = True

        while queue:
            w = queue.popleft()
            if w == dest:
                return True
            node = self.adjList[w]
            while node is not None:
                if visited[node.vertex] == False and node.weight >= box_weight:
                    visited[node.vertex] == True
                    queue.append(node.vertex)
                node = node.next
        return False

    def insertEdge2(self, v1, v2, w):   # list of lists
        self.adjList2[v1].append((v2, w))
        self.adjList2[v2].append((v1, w))

    def bfs2(self, start, dest, box_weight):
        visited = [False] * (self.size+1)
        queue = deque([start])
        visited[start] = True
        while queue:
            w = queue.popleft()
            if w == dest:
                return True
            for vertex, weight in self.adjList2[w]:
                if visited[vertex] == False and weight >= box_weight:
                    visited[vertex] = True
                    queue.append(vertex)
        return False


    def findFactory(self, start, dest, max_weight):
        left = 1
        right = max_weight
        answer = 0
        while left <= right:
            mid = (left+right)//2
            if self.bfs2(start, dest, mid) == True:
                answer = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return answer


n, m = map(int, stdin.readline().split())
g = Graph(n)
max_weight = 0
for _ in range(m):
    v1, v2, w = map(int, stdin.readline().split())
    if max_weight < w:      # 중량 최댓값 구하기
        max_weight = w
    g.insertEdge2(v1, v2, w)

f1, f2 = map(int, stdin.readline().split())
result = g.findFactory(f1, f2, max_weight)
print(result)