結果

問題 No.748 yuki国のお財布事情
ユーザー syunsuke
提出日時 2019-09-08 16:42:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,139 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 115,052 KB
最終ジャッジ日時 2024-06-27 15:03:38
合計ジャッジ時間 8,173 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 12 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

L=[[]for i in range(N+1)]
l=[[]]
C=[1 for i in range(N+1)]

for i in range(M):
    a,b,c=map(int,input().split())
    L[a].append((b,c))
    L[b].append((a,c))
    l.append([a,b,c])
z=[]
if K>0:
    for i in range(K):
        n=int(input())
        z.append(n)
else:
    x=0
    Z=10**9
    for i in range(1,M+1):
        if l[i][2]<Z:
            Z=l[i][2]
            x=i
    z.append(x)
    #print(l[x][0])

Q=[]
cost=0
for i in z:
    cost+=l[i][2]
    for k in range(2):
        if C[l[i][k]]==1:
            C[l[i][k]]=0
            for j in L[l[i][k]]:
                if C[j[0]]==1:
                    Q.append((j[1],j[0]))
#print(Q)
heapq.heapify(Q)

for i in range(10**6):
    if len(Q)==0:
        break
    else:
        if C[Q[0][1]]==1:
            x,y=Q[0]
            heapq.heappop(Q)
            C[y]=0
            cost+=x
            for j in L[y]:
                if C[j[0]]==1:
                    heapq.heappush(Q,(j[1],j[0]))
        else:
            heapq.heappop(Q)
#print(cost)
#print(len(l))
#print(l)
COST=0
for i in range(1,M+1):
    COST+=l[i][2]
print(COST-cost)
0