結果

問題 No.1639 最小通信路
コンテスト
ユーザー wolgnik
提出日時 2021-08-06 22:01:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,233 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 81,644 KB
実行使用メモリ 245,976 KB
最終ジャッジ日時 2024-09-17 01:59:49
合計ジャッジ時間 23,637 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline
N = int(input())
e = [[] for _ in range(N + 1)]
for _ in range(N * (N - 1) // 2):
  u, v, c = map(int, input().split())
  e[u].append((v, c, 0))
  e[v].append((u, c, 0))

import heapq
class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    b = pow(10, 6)
    for edge in e[1]:
      heapq.heappush(h, edge[1] * b ** 2 + edge[0] * b + edge[2])
    res = 0
    reslist = []
    visited[1] = 1
    while len(h):
      p = heapq.heappop(h)
      p01 = p // b
      p2 = p % b
      p0 = p01 // b
      p1 = p01 % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b ** 2 + q[0] * b + q[2])
      res += p0
      reslist.append(p2)
    return res, reslist

pri = prim(N, e)
cost = pri.MSTcost()[0]

ok = 10 ** 100
ng = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  me = [[] for _ in range(N + 1)]
  for x in range(1, N + 1):
    for y, c, _ in e[x]:
      if c <= m: me[x].append((y, c, 0))
  pri = prim(N, me)
  mst = pri.MSTcost()
  if mst[0] == cost and len(mst[1]) == N - 1: ok = m
  else: ng = m
print(ok)
0