728x90 Bellman-Ford1 [파이썬] 1865 웜홀 (백준) 1. 문제 설명 문제 : 1865 - 웜홀 https://www.acmicpc.net/problem/1865 (골3) 사용 언어 : 파이썬 (Pypy3) 사용 알고리즘 : 벨만-포드 알고리즘 문제요약 : M개의 양방향 간선인 도로와 W개의 단방향 간선인 웜홀이 이들을 지나는 시간과 함께 주어졌을 때, 음의 사이클이 있는지 구하여라. 2. 문제 풀이 해설 : 음의 사이클을 찾을 수 있는 벨만포드 알고리즘을 이용한다. 여기서 주의해야 할 점이 있는데, 일반 벨만포드 코드와 다르게 아래 코드를 삭제해야 한다. distance[now_node] != INF 왜냐하면 위 코드는 'start'라는 지점에서부터 연결된 각 노드까지의 최단 경로를 구하는 코드이다. 하지만 이 문제에서는 시작 지점이 주어지지 않고, 음의.. 2023. 12. 28. 이전 1 다음 728x90
