🐸 문제 정보
1865번: 웜홀
첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),
www.acmicpc.net
🤖 알고리즘
벨만포드
⏱️ 풀이 시간
26.27m
📝 풀이
벨만포드 알고리즘을 이용하면 쉽게(?) 풀 수 있는 문제였다.
그럼에도 오래걸린 이유는 INF 값의 처리 때문이었다...
여튼 해당 몬제에서 유의할 점은 아래와 같다.
- 도로의 경우, 양방향이기 때문에 시작점과 끝점 총 두번을 append 해줘야한다.
- 웜홀은 단방향이지만, 가중치가 음수이다.
- 어느점에서 시작해도 상관없다. cycle이 발생하는지 여부에 따라 음수 가중치로 끝날지 결정되기 때문이다.
최단 경로 찾기 with Python
🌊 최단 경로 찾기 알고리즘 🐸 이해하기 최단경로 찾기 알고리즘? 노드 간 가중치가 주어질 때, 시작 노드부터 모든 노드까지의 최소값을 구하는 알고리즘이다. 이해하는데에 큰 어려움은 없
99uulog.tistory.com
🧑💻 나의 답
# pypy3
import sys
input = sys.stdin.readline
INF = sys.maxsize
def bellman(start):
distance[start] = 0
for i in range(n):
for s, e, t in graph:
dist = distance[s] + t
if dist < distance[e]:
if i == n - 1:
return True
distance[e] = dist
return False
for _ in range(int(input().rstrip())):
n, m, w = list(map(int, input().rstrip().split()))
graph = []
distance = [INF] * (n + 1)
for _ in range(m): # 도로 -> 양방향
s, e, t = list(map(int, input().rstrip().split()))
graph.append((s, e, t))
graph.append((e, s, t))
for _ in range(w): # 웜홀 -> 단방향
s, e, t = list(map(int, input().rstrip().split()))
graph.append((s, e, -t))
if bellman(1):
print('YES')
else:
print('NO')