풀이
가중치가 양수인 간선은 양방향, 음수인 간선은 단방향인 그래프에서
출발 정점에서 도착 정점까지 돌아오는 음수사이클이 존재하는지 확인하면 되는 문제다.
특이한 점이라 하면 출발점이 주어지지 않았고, 그래프 내에 어디든 상관없이 조건에 부합하는 음수 사이클이 존재하는지 여부만 알면 되는 문제다.
때문에 모든 정점을 출발점으로 간주하고 bellman ford를 여러 번 진행해야 한다.
만약 탐색 후 dist가 inf가 아니라면, 이미 탐색을 한 번 완료한 그래프이기에, 탐색이 되지 않은 또 다른 그래프에 대해서만 탐색을 진행해주었다.
좀 더 빠르게 탐색해보자.
어떤 정점을 기준으로 조건에 부합하는 음수 사이클이 존재하는지 모르기 때문에, 어차피 모든 정점에 대한 탐색이 이루어져야 하며 매 탐색마다 시작 정점의 가중치는 0이 된다.
즉, 모든 정점에 대한 탐색이 이루어지기 때문에 모든 정점에 방문할 것이고, 최단거리가 갱신되지 않은 정점에 대해 inf로 설정해줄 필요가 없다.
모든 정점의 초기 최단거리를 0으로 초기화해주자.
또한, 간선에 대한 정보를 입력받는 부분을 다음과 같이 수정했다.
이제 N개의 출발점에 대해 최단거리 갱신하는 과정을 진행해보자.
다음과 같이 개선이 이루어졌다.
소스코드
출처
1865번: 웜홀
첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 25192] 인사성 밝은 곰곰이 [Java] (0) | 2023.06.20 |
|---|---|
| [백준 2096] 내려가기 [Python] (0) | 2023.06.18 |
| [백준 3932] Unreliable Messengers [Python] (0) | 2023.06.16 |
| [백준 28224] Final Price [Python] (0) | 2023.06.15 |
| [백준 1298] 노트북의 주인을 찾아서 [Python] (0) | 2023.06.14 |