結果

問題 No.748 yuki国のお財布事情
ユーザー syunsukesyunsuke
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
53,932 KB
testcase_01 AC 40 ms
53,020 KB
testcase_02 AC 39 ms
53,548 KB
testcase_03 AC 43 ms
54,368 KB
testcase_04 AC 40 ms
53,008 KB
testcase_05 AC 40 ms
53,036 KB
testcase_06 AC 40 ms
52,740 KB
testcase_07 AC 40 ms
53,348 KB
testcase_08 AC 39 ms
52,948 KB
testcase_09 AC 40 ms
53,556 KB
testcase_10 AC 40 ms
53,496 KB
testcase_11 AC 41 ms
54,852 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 39 ms
53,228 KB
testcase_24 AC 39 ms
53,076 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 465 ms
105,896 KB
testcase_28 AC 378 ms
102,620 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