結果

問題 No.2914 正閉路検出
ユーザー titia
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 35 WA * 20
権限があれば一括ダウンロードができます

ソースコード

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