結果

問題 No.748 yuki国のお財布事情
ユーザー titia
提出日時 2018-10-19 23:34:00
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,721 bytes
コンパイル時間 315 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 64,128 KB
最終ジャッジ日時 2024-11-18 22:45:18
合計ジャッジ時間 13,247 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 11 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,M,K=map(int,input().split())

ABC=[list(map(int,input().split())) for i in range(M)]
E=[int(input()) for i in range(K)]

S=[0 for i in range(M+1)]
for e in E:
    S[e]=1

SAMELIST=[i for i in range(N+1)]
def find(a):
    while SAMELIST[a]!=a:
        a=SAMELIST[a]
    return a

def 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 E:
    Union(ABC[e-1][0],ABC[e-1][1])
    #print(ABC[e-1][0],ABC[e-1][1],SAMELIST)

from collections import defaultdict
EDGE=[defaultdict(int) for i in range(N+1)]


ANS=0
for i in range(M):
    a,b,c=ABC[i]
    #print(a,b,c,find(a),find(b))
    if find(a)==find(b) and S[i+1]!=1:
        ANS+=c
        continue
    if find(a)==find(b):
        continue
    
    if EDGE[find(a)][find(b)]!=0:
        if EDGE[find(a)][find(b)]>c:
            ANS+=EDGE[find(a)][find(b)]
            EDGE[find(a)][find(b)]=c
            EDGE[find(b)][find(a)]=c
        else:
            ANS+=c
    else:
        EDGE[find(a)][find(b)]=c
        EDGE[find(b)][find(a)]=c

from collections import deque
QUE=deque([1])
checked=[0]*(N+1)
DELCOST=[-1]*(N+1)

#print(ANS,EDGE)

while QUE:
    x=QUE.pop()
    checked[x]=1

    for to in EDGE[x]:
        if checked[to]==1:
            continue
        elif DELCOST[to]==-1:
            DELCOST[to]=EDGE[x][to]
            QUE.append(to)
        elif DELCOST[to]>EDGE[x][to]:
            ANS+=DELCOST[to]
            DELCOST[to]=EDGE[x][to]
            QUE.append(to)
        else:
            ANS+=EDGE[x][to]
            QUE.append(to)

        #print(ANS,EDGE,x,to)

print(ANS)
0