군사 이동

• 문제 설명이 살짝 헷갈릴 수 있는데, c에서 v로 가는 경로중에서 가장 좁은 길의 너비가 최대가 되는 경로를 찾으라는 뜻이다
• 엣지들을 내림차순으로 정렬한 뒤, c와 v가 연결될때까지 하나씩 추가해보다가 연결되는 순간 추가된 엣지를 출력하면 된다. 연결 여부는 Disjoint Set을 사용한다. 엣지를 정렬하고 하나씩 추가하면서 disjoint set을 업데이트 하는 것은 크루스칼 알고리즘의 아이디어와도 살짝 비슷한 느낌이다.
• 지점의 갯수가 n, 길의 갯수가 m일때, 길을 정렬하는데에 O(mlogm)이 걸리고, 정렬된 길들 최대 m개 추가하면서 연결성을 확인하는 데에는 O(m*α(n))이 걸린다. 총 시간 복잡도는 O(m*(α(n)+logm))

"""Solution code for "BOJ 11085. 군사 이동".

- Problem link: https://www.acmicpc.net/problem/11085
- Solution link: http://www.teferi.net/ps/problems/boj/11085

Tags: [DisjointSet]
"""

import sys
from teflib import disjointset


def main():
    p, w = [int(x) for x in sys.stdin.readline().split()]
    c, v = [int(x) for x in sys.stdin.readline().split()]
    dsu = disjointset.DisjointSet(p)
    walkways = []
    for _ in range(w):
        w_start, w_end, w_width = [int(x) for x in sys.stdin.readline().split()]
        walkways.append((w_width, w_start, w_end))
    walkways.sort(reverse=True)
    for w_width, w_start, w_end in walkways:
        dsu.union(w_start, w_end)
        if dsu.find(c) == dsu.find(v):
            print(w_width)
            break


if __name__ == '__main__':
    main()

• Dependency: teflib.disjointset.DisjointSet