結果

問題 No.2914 正閉路検出
ユーザー titiatitia
提出日時 2024-10-27 04:47:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,067 bytes
コンパイル時間 428 ms
コンパイル使用メモリ 82,856 KB
実行使用メモリ 144,916 KB
最終ジャッジ日時 2024-10-27 04:48:07
合計ジャッジ時間 17,775 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
54,672 KB
testcase_01 AC 39 ms
54,260 KB
testcase_02 AC 36 ms
53,364 KB
testcase_03 AC 37 ms
53,200 KB
testcase_04 AC 36 ms
53,028 KB
testcase_05 AC 37 ms
53,160 KB
testcase_06 AC 36 ms
53,312 KB
testcase_07 AC 37 ms
53,532 KB
testcase_08 AC 36 ms
53,212 KB
testcase_09 AC 36 ms
52,936 KB
testcase_10 AC 38 ms
54,676 KB
testcase_11 WA -
testcase_12 AC 38 ms
53,504 KB
testcase_13 WA -
testcase_14 AC 38 ms
54,032 KB
testcase_15 AC 38 ms
53,884 KB
testcase_16 AC 39 ms
53,012 KB
testcase_17 AC 38 ms
54,168 KB
testcase_18 WA -
testcase_19 AC 90 ms
82,248 KB
testcase_20 AC 133 ms
91,648 KB
testcase_21 AC 77 ms
77,304 KB
testcase_22 AC 150 ms
98,376 KB
testcase_23 AC 92 ms
81,888 KB
testcase_24 AC 164 ms
105,552 KB
testcase_25 AC 56 ms
73,104 KB
testcase_26 AC 64 ms
77,292 KB
testcase_27 AC 184 ms
103,060 KB
testcase_28 AC 282 ms
112,324 KB
testcase_29 AC 469 ms
122,536 KB
testcase_30 AC 133 ms
87,480 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 AC 192 ms
121,252 KB
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 AC 240 ms
121,252 KB
testcase_52 AC 197 ms
120,780 KB
testcase_53 AC 201 ms
120,636 KB
testcase_54 AC 200 ms
120,872 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

from heapq import heappop,heappush

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

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

E=[[] for i in range(N+1)]

for i in range(M):
    x,y,d=EDGE[i]
    E[x].append((y,d,i+1))
    E[y].append((x,-d,i+1))

D=[-(1<<63)]*(N+1)
FROM=[-(1<<63)]*(N+1)
flag=0
lastroute=-1
for i in range(1,N+1):
    if D[i]==-1<<63:
        D[i]=0
        Q=[(0,i)]

        while Q:
            now,ind=heappop(Q)
            #print(Q,ind,now,D,FROM)
            #print(ind)

            for to,dis,route in E[ind]:
                if D[to]!=-1<<63 and D[to]!=now+dis:
                    #print("!!",to)
                    lastroute=(ind,to,route)
                    flag=1
                    ANS=to
                    break
                elif D[to]<now+dis:
                    D[to]=now+dis
                    heappush(Q,(D[to],to))
                    FROM[to]=(ind,route)

            if flag==1:
                break

    if flag==1:
        break

if lastroute==-1:
    print(-1)
    exit()

#print(ANS,lastroute)

NODE=[lastroute[0]]
ROUTE=[]

now=lastroute[0]

while True:
    if FROM[now]==-1<<63:
        break
    ind,route=FROM[now]
    NODE.append(ind)
    ROUTE.append(route)

    now=ind

    if now==lastroute[0] or now==lastroute[1]:
        break

NODE2=[lastroute[1]]
ROUTE2=[]

now=lastroute[1]

while True:
    if FROM[now]==-1<<63:
        break
    ind,route=FROM[now]
    NODE2.append(ind)
    ROUTE2.append(route)

    now=ind

    if now==lastroute[0] or now==lastroute[1]:
        break

SET=set(NODE2)

for i in range(len(NODE)):
    if NODE[i] in SET:
        p=NODE[i]
        break

k=NODE.index(p)
R=ROUTE[:k]

k=NODE2.index(p)
R2=ROUTE2[:k]

ANS=R+[lastroute[2]]+R2[::-1]
now=p
score=0
for ans in ANS:
    x,y,d=EDGE[ans-1]

    if now==x:
        score+=d
        now=y
    elif now==y:
        score-=d
        now=x
    else:
        exit()

if score>0:
    print(len(ANS))
    print(p)
    print(*ANS)
else:
    print(len(ANS))
    print(p)
    print(*ANS[::-1])
0