結果
問題 | No.1473 おでぶなおばけさん |
ユーザー |
|
提出日時 | 2022-05-31 11:17:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 714 ms / 2,000 ms |
コード長 | 999 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 82,440 KB |
実行使用メモリ | 107,080 KB |
最終ジャッジ日時 | 2024-09-21 01:15:06 |
合計ジャッジ時間 | 21,793 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
import sys sys.setrecursionlimit(10 ** 8) n,m = map(int,input().split()) edge = [] for _ in range(m): s,t,d = map(int,input().split()) s -= 1 t -= 1 edge.append((s,t,d)) edge.sort(key = lambda x:x[2]) parent = list(range(n)) def find(i): if parent[i] == i:return i parent[i] = find(parent[i]) return parent[i] def unite(i,j): I = find(i) J = find(j) if I == J:return False parent[I] = J parent[i] = J return True def isSame(i,j): return find(i) == find(j) ans = 0 G = [[] for _ in range(n)] while not isSame(0,n-1): s,t,d = edge.pop() ans = d G[s].append(t) G[t].append(s) unite(s,t) while edge and edge[-1][2] == ans: s,t,d = edge.pop() G[s].append(t) G[t].append(s) from collections import deque q = deque() q.append(0) dist = [-1] * n dist[0] = 0 while q: now = q.popleft() for v in G[now]: if dist[v] == -1: dist[v] = dist[now] + 1 q.append(v) print(ans,dist[-1])