結果

問題 No.2914 正閉路検出
ユーザー titiatitia
提出日時 2024-10-27 04:53:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,089 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 142,912 KB
最終ジャッジ日時 2024-10-27 04:53:40
合計ジャッジ時間 17,495 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,012 KB
testcase_01 AC 39 ms
53,576 KB
testcase_02 AC 39 ms
54,728 KB
testcase_03 AC 40 ms
53,604 KB
testcase_04 AC 38 ms
53,744 KB
testcase_05 AC 39 ms
53,784 KB
testcase_06 AC 38 ms
53,916 KB
testcase_07 AC 38 ms
53,616 KB
testcase_08 AC 40 ms
53,932 KB
testcase_09 AC 39 ms
54,220 KB
testcase_10 AC 38 ms
53,340 KB
testcase_11 AC 39 ms
53,168 KB
testcase_12 AC 38 ms
53,620 KB
testcase_13 WA -
testcase_14 AC 39 ms
53,440 KB
testcase_15 AC 39 ms
53,612 KB
testcase_16 AC 40 ms
54,060 KB
testcase_17 AC 38 ms
53,748 KB
testcase_18 WA -
testcase_19 AC 92 ms
82,100 KB
testcase_20 AC 131 ms
91,652 KB
testcase_21 AC 71 ms
77,352 KB
testcase_22 AC 150 ms
98,884 KB
testcase_23 AC 94 ms
81,664 KB
testcase_24 AC 164 ms
106,048 KB
testcase_25 AC 59 ms
73,432 KB
testcase_26 AC 68 ms
77,396 KB
testcase_27 AC 212 ms
103,128 KB
testcase_28 AC 281 ms
112,080 KB
testcase_29 AC 483 ms
122,684 KB
testcase_30 AC 138 ms
87,484 KB
testcase_31 AC 205 ms
102,556 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 AC 212 ms
120,376 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 215 ms
120,588 KB
testcase_52 AC 216 ms
120,640 KB
testcase_53 AC 208 ms
121,072 KB
testcase_54 AC 208 ms
121,116 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)
            now=-now
            #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