結果

問題 No.748 yuki国のお財布事情
ユーザー syunsukesyunsuke
提出日時 2019-09-08 16:42:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,139 bytes
コンパイル時間 464 ms
コンパイル使用メモリ 87,084 KB
実行使用メモリ 117,396 KB
最終ジャッジ日時 2023-09-09 22:33:17
合計ジャッジ時間 9,152 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
71,352 KB
testcase_01 AC 72 ms
71,132 KB
testcase_02 AC 73 ms
70,924 KB
testcase_03 AC 72 ms
70,928 KB
testcase_04 AC 72 ms
71,192 KB
testcase_05 AC 72 ms
71,328 KB
testcase_06 AC 72 ms
71,300 KB
testcase_07 AC 74 ms
71,096 KB
testcase_08 AC 72 ms
71,212 KB
testcase_09 AC 73 ms
71,184 KB
testcase_10 AC 74 ms
71,248 KB
testcase_11 AC 73 ms
71,088 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 RE -
testcase_23 AC 74 ms
71,404 KB
testcase_24 AC 75 ms
71,344 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 449 ms
108,280 KB
testcase_28 AC 378 ms
103,112 KB
権限があれば一括ダウンロードができます

ソースコード

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