結果

問題 No.748 yuki国のお財布事情
ユーザー titiatitia
提出日時 2018-10-19 23:34:00
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,721 bytes
コンパイル時間 315 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 64,128 KB
最終ジャッジ日時 2024-11-18 22:45:18
合計ジャッジ時間 13,247 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 26 ms
17,824 KB
testcase_01 AC 27 ms
10,880 KB
testcase_02 AC 28 ms
11,136 KB
testcase_03 AC 26 ms
11,008 KB
testcase_04 AC 29 ms
11,008 KB
testcase_05 AC 27 ms
11,008 KB
testcase_06 AC 26 ms
11,008 KB
testcase_07 AC 27 ms
11,136 KB
testcase_08 AC 26 ms
11,136 KB
testcase_09 AC 28 ms
11,136 KB
testcase_10 AC 27 ms
11,008 KB
testcase_11 AC 26 ms
11,136 KB
testcase_12 AC 27 ms
11,008 KB
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 AC 27 ms
10,880 KB
testcase_23 AC 28 ms
11,008 KB
testcase_24 AC 26 ms
11,008 KB
testcase_25 TLE -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 667 ms
42,192 KB
権限があれば一括ダウンロードができます

ソースコード

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