結果

問題 No.1473 おでぶなおばけさん
ユーザー brthyyjpbrthyyjp
提出日時 2021-04-09 21:43:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,521 bytes
コンパイル時間 444 ms
コンパイル使用メモリ 87,028 KB
実行使用メモリ 115,716 KB
最終ジャッジ日時 2023-09-07 10:35:57
合計ジャッジ時間 22,240 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 97 ms
71,156 KB
testcase_01 AC 96 ms
71,156 KB
testcase_02 AC 666 ms
112,892 KB
testcase_03 AC 575 ms
112,384 KB
testcase_04 AC 459 ms
97,824 KB
testcase_05 AC 287 ms
85,332 KB
testcase_06 AC 516 ms
104,644 KB
testcase_07 AC 716 ms
115,704 KB
testcase_08 AC 742 ms
115,716 KB
testcase_09 AC 637 ms
111,676 KB
testcase_10 AC 249 ms
94,320 KB
testcase_11 AC 247 ms
94,356 KB
testcase_12 AC 243 ms
94,312 KB
testcase_13 AC 195 ms
88,292 KB
testcase_14 AC 168 ms
84,952 KB
testcase_15 AC 246 ms
95,244 KB
testcase_16 AC 245 ms
94,072 KB
testcase_17 AC 116 ms
78,420 KB
testcase_18 AC 121 ms
79,632 KB
testcase_19 AC 372 ms
91,912 KB
testcase_20 AC 576 ms
105,756 KB
testcase_21 AC 528 ms
102,064 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 626 ms
114,000 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 656 ms
112,364 KB
testcase_32 AC 473 ms
108,896 KB
testcase_33 AC 545 ms
103,216 KB
testcase_34 AC 419 ms
92,340 KB
testcase_35 AC 331 ms
91,620 KB
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 AC 249 ms
93,952 KB
testcase_40 AC 246 ms
94,452 KB
testcase_41 AC 243 ms
93,896 KB
testcase_42 AC 240 ms
94,204 KB
testcase_43 AC 215 ms
102,340 KB
testcase_44 AC 212 ms
102,244 KB
testcase_45 AC 213 ms
102,272 KB
testcase_46 AC 563 ms
101,808 KB
testcase_47 AC 678 ms
109,796 KB
testcase_48 AC 553 ms
103,304 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [0]*n

    def Find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.Find(self.par[x])
            return self.par[x]

    def Unite(self, x, y):
        x = self.Find(x)
        y = self.Find(y)

        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x]
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def Same(self, x, y):
        return self.Find(x) == self.Find(y)

    def Size(self, x):
        return -self.par[self.Find(x)]

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, m = map(int, input().split())
edge = []
for i in range(m):
    s, t, d = map(int, input().split())
    s, t = s-1, t-1
    edge.append((s, t, d))

edge.sort(key=lambda x: -x[2])
M = 10**18
uf = UnionFind(n)
g = [[] for i in range(n)]
for s, t, d in edge:
    if uf.Same(0, n-1):
        break
    else:
        uf.Unite(s, t)
        M = min(M, d)
        g[s].append(t)
        g[t].append(s)
#print(M)
from collections import deque
q = deque([])
q.append(0)
dist = [-1]*n
dist[0] = 0
while q:
    v = q.popleft()
    for u in g[v]:
        if dist[u] == -1:
            q.append(u)
            dist[u] = dist[v]+ 1
print(M, dist[n-1])
0