結果

問題 No.2914 正閉路検出
ユーザー titiatitia
提出日時 2024-10-29 03:18:49
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,315 ms / 2,000 ms
コード長 1,869 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 86,988 KB
最終ジャッジ日時 2024-10-29 03:19:23
合計ジャッジ時間 32,129 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
11,008 KB
testcase_01 AC 32 ms
11,008 KB
testcase_02 AC 29 ms
11,008 KB
testcase_03 AC 30 ms
11,008 KB
testcase_04 AC 30 ms
11,008 KB
testcase_05 AC 31 ms
11,136 KB
testcase_06 AC 31 ms
11,008 KB
testcase_07 AC 30 ms
11,008 KB
testcase_08 AC 30 ms
11,008 KB
testcase_09 AC 29 ms
11,008 KB
testcase_10 AC 29 ms
11,008 KB
testcase_11 AC 31 ms
11,136 KB
testcase_12 AC 30 ms
11,008 KB
testcase_13 AC 30 ms
11,008 KB
testcase_14 AC 31 ms
11,008 KB
testcase_15 AC 31 ms
11,008 KB
testcase_16 AC 32 ms
11,136 KB
testcase_17 AC 31 ms
11,008 KB
testcase_18 AC 31 ms
11,136 KB
testcase_19 AC 135 ms
16,000 KB
testcase_20 AC 257 ms
23,040 KB
testcase_21 AC 88 ms
13,568 KB
testcase_22 AC 308 ms
25,984 KB
testcase_23 AC 232 ms
21,376 KB
testcase_24 AC 359 ms
28,800 KB
testcase_25 AC 55 ms
11,904 KB
testcase_26 AC 74 ms
12,928 KB
testcase_27 AC 425 ms
32,384 KB
testcase_28 AC 491 ms
37,120 KB
testcase_29 AC 939 ms
67,328 KB
testcase_30 AC 153 ms
28,544 KB
testcase_31 AC 461 ms
32,640 KB
testcase_32 AC 510 ms
38,272 KB
testcase_33 AC 166 ms
30,848 KB
testcase_34 AC 1,154 ms
76,928 KB
testcase_35 AC 1,152 ms
77,184 KB
testcase_36 AC 1,146 ms
77,184 KB
testcase_37 AC 977 ms
86,988 KB
testcase_38 AC 761 ms
71,296 KB
testcase_39 AC 1,204 ms
85,248 KB
testcase_40 AC 1,220 ms
85,760 KB
testcase_41 AC 1,220 ms
85,404 KB
testcase_42 AC 1,315 ms
86,016 KB
testcase_43 AC 1,211 ms
86,660 KB
testcase_44 AC 1,185 ms
85,024 KB
testcase_45 AC 1,238 ms
86,344 KB
testcase_46 AC 1,215 ms
86,272 KB
testcase_47 AC 1,229 ms
86,016 KB
testcase_48 AC 1,187 ms
85,248 KB
testcase_49 AC 1,241 ms
86,440 KB
testcase_50 AC 1,241 ms
86,144 KB
testcase_51 AC 660 ms
64,128 KB
testcase_52 AC 680 ms
66,432 KB
testcase_53 AC 654 ms
66,304 KB
testcase_54 AC 666 ms
66,304 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

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

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

Group = [i for i in range(N+1)] # グループ分け
Nodes = [1]*(N+1) # 各グループのノードの数
Weight = [0]*(N+1) # 木の親からnode xまでの距離

def find(x):
    ANS=Weight[x]
    while Group[x] != x:
        x=Group[x]
        ANS+=Weight[x]
    return x,ANS

def Union(x,y,z): # xからyの距離がz
    if find(x)[0] != find(y)[0]:
        if Nodes[find(x)[0]] < Nodes[find(y)[0]]:
            Weight[find(x)[0]]=-z+find(y)[1]-find(x)[1]
            
            Nodes[find(y)[0]] += Nodes[find(x)[0]]
            Nodes[find(x)[0]] = 0
            Group[find(x)[0]] = find(y)[0]
            
        else:
            Weight[find(y)[0]]=z+find(x)[1]-find(y)[1]
            
            Nodes[find(x)[0]] += Nodes[find(y)[0]]
            Nodes[find(y)[0]] = 0
            Group[find(y)[0]] = find(x)[0]

E=[[] for i in range(N+1)]
x0,y0=-1,-1

for i in range(M):
    x,y,w = EDGE[i]
    if find(x)[0]!=find(y)[0]:
        Union(x,y,w)
        E[x].append((y,w,i+1))
        E[y].append((x,-w,i+1))
    else:
        kx=find(x)[1]
        ky=find(y)[1]

        if ky-kx==w:
            pass
        else:
            x0,y0=x,y
            last=i+1
            lastw=w

if x0==-1 and y0==-1:
    print(-1)
    exit()

now=x0
ANS=[]
USE=[0]*(N+1)
USE[now]=1
Q=[now]
FROM=[-1]*(N+1)
C=[0]*(N+1)

while Q:
    x=Q.pop()

    for to,cost,ind in E[x]:
        if USE[to]==0:
            FROM[to]=(x,ind)
            C[to]=C[x]+cost
            Q.append(to)
            USE[to]=1
            
ANS=[]

now=y0
while now!=x0:
    fr,ind=FROM[now]
    ANS.append(ind)
    now=fr

if C[y0]-lastw<0:
    print(len(ANS)+1)
    print(x0)
    print(*[last]+ANS)
else:
    print(len(ANS)+1)
    print(x0)
    print(*([last]+ANS)[::-1])
0