結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2018-10-20 07:03:23 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,184 ms / 2,000 ms |
コード長 | 1,259 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 58,976 KB |
最終ジャッジ日時 | 2024-11-19 01:54:36 |
合計ジャッジ時間 | 12,062 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
N,M,K=map(int,input().split())ROAD=[list(map(int,input().split())) for i in range(M)]exc=[int(input()) for i in range(K)]S=[0 for i in range(M+1)]for e in exc:S[e]=1SAMELIST=[i for i in range(N+1)]def find(a):while SAMELIST[a]!=a:a=SAMELIST[a]return adef Union(x,y):if find(x)!=find(y):SAMELIST[find(x)]=min(find(y),find(x))SAMELIST[find(y)]=min(find(y),find(x))SAMELIST[x]=min(find(y),find(x))SAMELIST[y]=min(find(y),find(x))for e in exc:Union(ROAD[e-1][0],ROAD[e-1][1])from collections import defaultdictEDGE=defaultdict(int)ANS=0for i in range(M):a,b,c=ROAD[i]if a>b:a,b=b,aif find(a)==find(b) and S[i+1]!=1:ANS+=ccontinueelif find(a)==find(b):continueelif EDGE[find(a),find(b)]!=0:if EDGE[find(a),find(b)]>c:ANS+=EDGE[find(a),find(b)]EDGE[find(a),find(b)]=celse:ANS+=celse:EDGE[find(a),find(b)]=cEDGE=sorted(list(EDGE.items()),key=lambda x:x[1])from collections import dequeQUE=deque(EDGE)while QUE:(a,b),cost=QUE.popleft()if find(a)==find(b):ANS+=costelse:Union(a,b)print(ANS)