BOJ 1738 골목길(Python 3)

https://www.acmicpc.net/problem/1738

이 문제는 오민식의 고민과 비슷한 문제이다.

음수 싸이클이 있을 경우 큐에 싸이클을 도는 정점을 모두 넣어주고, 큐에 있는 정점들이 코레스코 콘도까지 갈 수 있는지 없는지 확인해준다.(BFS)

만약 음수 싸이클에서 코레스코 콘도로 갈 수 있으면 -1을 출력

시작점에서 코레스코 콘도까지 갈 수 없으면 -1을 출력

갈 수 있으면 경로 리스트를 출력하면 된다.

경로 리스트는 리스트에 넣어둔 좌표를 역추적을 하여 출력하였다.

벨만포드 + BFS로 풀음

코드 확인

from collections import deque
input=__import__('sys').stdin.readline
n,m=map(int,input().split())
S=[[float('inf')]*2 for _ in range(n+1)]
D=[[] for _ in range(n+1)]
cycle=False
for i in range(m):
    u,v,w=map(int,input().split())
    D[u].append((v,-w))
S[1][0]=0
q=deque()
V=[0]*(n+1)
for i in range(n):
    for x in range(1,n+1):
        for nx,nt in D[x]:
            if S[nx][0]>S[x][0]+nt:
                S[nx][0]=S[x][0]+nt
                S[nx][1]=x
                if i==n-1:
                    V[x]=1
                    q.append(x)
while q:
    x=q.popleft()
    for nx,nt in D[x]:
        if V[nx]==0:
            V[nx]=1
            q.append(nx)
if S[n][0]==float('inf') or V[n]==1:print(-1)
else:
    Z=[n]
    b=n
    while 1:
        Z.append(S[b][1])
        b=S[b][1]
        if b==1:break
    print(' '.join(map(str,Z[::-1])))