結果

問題 No.2914 正閉路検出
ユーザー titiatitia
提出日時 2024-10-27 04:41:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,030 bytes
コンパイル時間 419 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 144,792 KB
最終ジャッジ日時 2024-10-27 04:42:05
合計ジャッジ時間 21,371 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,580 KB
testcase_01 AC 38 ms
53,496 KB
testcase_02 AC 37 ms
52,820 KB
testcase_03 AC 38 ms
53,168 KB
testcase_04 AC 38 ms
54,236 KB
testcase_05 AC 38 ms
53,356 KB
testcase_06 AC 39 ms
54,728 KB
testcase_07 WA -
testcase_08 AC 38 ms
53,252 KB
testcase_09 AC 39 ms
54,128 KB
testcase_10 AC 39 ms
54,308 KB
testcase_11 WA -
testcase_12 AC 38 ms
54,860 KB
testcase_13 WA -
testcase_14 AC 41 ms
53,796 KB
testcase_15 AC 39 ms
53,148 KB
testcase_16 AC 39 ms
53,672 KB
testcase_17 AC 40 ms
54,160 KB
testcase_18 WA -
testcase_19 AC 99 ms
82,076 KB
testcase_20 AC 155 ms
91,720 KB
testcase_21 AC 73 ms
77,768 KB
testcase_22 AC 157 ms
98,520 KB
testcase_23 AC 94 ms
81,784 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 68 ms
77,372 KB
testcase_27 AC 208 ms
103,104 KB
testcase_28 AC 291 ms
112,404 KB
testcase_29 AC 491 ms
122,540 KB
testcase_30 AC 136 ms
88,200 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 195 ms
121,436 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 218 ms
120,856 KB
testcase_52 AC 204 ms
120,892 KB
testcase_53 WA -
testcase_54 AC 209 ms
120,844 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(ind)

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

            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