結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:43:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 516 ms / 2,000 ms
コード長 2,025 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 126,428 KB
最終ジャッジ日時 2025-03-20 18:43:29
合計ジャッジ時間 16,763 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.size = [1] * size
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    m = int(input[idx])
    idx += 1
    
    edges = []
    original_edges = []
    for _ in range(m):
        s = int(input[idx])
        idx += 1
        t = int(input[idx])
        idx += 1
        d = int(input[idx])
        idx += 1
        edges.append( (d, s-1, t-1) )
        original_edges.append( (s, t, d) )
    
    # Sort edges in descending order of d
    edges.sort(reverse=True, key=lambda x: x[0])
    
    uf = UnionFind(n)
    max_w = 0
    found = False
    
    for d, s, t in edges:
        uf.unite(s, t)
        if uf.find(0) == uf.find(n-1):
            max_w = d
            found = True
            break
    
    assert found
    
    # Build adjacency list using original edges with d >= max_w
    adj = [[] for _ in range(n)]
    for s, t, d in original_edges:
        if d >= max_w:
            s_idx = s - 1
            t_idx = t - 1
            adj[s_idx].append(t_idx)
            adj[t_idx].append(s_idx)
    
    # BFS to find the shortest path
    visited = [-1] * n
    q = deque()
    q.append(0)
    visited[0] = 0
    
    while q:
        v = q.popleft()
        if v == n - 1:
            break
        for u in adj[v]:
            if visited[u] == -1:
                visited[u] = visited[v] + 1
                q.append(u)
    
    min_steps = visited[n-1]
    print(max_w, min_steps)

if __name__ == "__main__":
    main()
0