結果

問題 No.748 yuki国のお財布事情
ユーザー DrDrpilotDrDrpilot
提出日時 2022-01-20 11:26:32
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 894 ms / 2,000 ms
コード長 1,407 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 45,184 KB
最終ジャッジ日時 2024-11-23 14:28:53
合計ジャッジ時間 10,827 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class UnionFind:
def __init__(self, n):
self.n=n
self.parent_size=[-1]*n
def merge(self, a, b):
x, y=self.leader(a), self.leader(b)
if x == y: return
if abs(self.parent_size[x])<abs(self.parent_size[y]): x, y=y, x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y]=x
return
def same(self, a, b):
return self.leader(a) == self.leader(b)
def leader(self, a):
if self.parent_size[a]<0: return a
self.parent_size[a]=self.leader(self.parent_size[a])
return self.parent_size[a]
def size(self, a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result=[[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r != []]
n,m,k=map(int,input().split())
uni=UnionFind(n)
total=0
path=[]
for i in range(m):
a,b,c=map(int,input().split())
a-=1;b-=1
path.append([c,a,b,i+1])
total+=c
hozon=set()
for _ in range(k):
e=int(input())
hozon.add(e)
path2=[]
minmum_cost=0
for cost,a,b,ind in path:
if ind in hozon:
uni.merge(a,b)
minmum_cost+=cost
else:
path2.append([cost,a,b])
path2.sort()
for cost,a,b in path2:
if uni.same(a,b):
continue
minmum_cost+=cost
uni.merge(a,b)
print(total-minmum_cost)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0