BOJ - 1865 ) 웜홀

 

---

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

1865번: 웜홀

---

MCMF(Minimum Cost Maximum Flow)를 위한 SPFA(Shortest Path Faster Algorithm) 공부중 푼문제

 

1-N 의 정점에서 SPFA를 실행하여 음의 사이클이 있는지 확인한다. 

 

SPFA는 벨만-포드 알고리즘과 유사하게 작동하는데, 벨만 포드가 모든 간선에대해서 경로 업데이트를 진행한다면

SPFA는 변화가 있는 노드를 큐에넣고 큐가 더이상 진행되지 않을때까지 경로 업데이트를 진행한다.

 

벨만 포드 알고리즘에서 V-1번 이후 경로업데이트가 이루어지면 음의 사이클을 존재함을 판단하는데

SPFA에서는 특정노드를 N번 이상 방문한다면 음의 사이클이 존재함을 판단한다.

---

package algorithm_2022;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_1865 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(st.nextToken());
		for(int i=0;i<T;) {
			
			st = new StringTokenizer(br.readLine());
			
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int W = Integer.parseInt(st.nextToken());
			
			ArrayList<int []> nodes[] = new ArrayList[N];
 			for(int j=0;j<N;) {
 				nodes[j] = new ArrayList<>();
 				++j;
 			}
			
 			for(int j=0;j<M;) {
 				st = new StringTokenizer(br.readLine());
 				int S = Integer.parseInt(st.nextToken())-1;
 				int E = Integer.parseInt(st.nextToken())-1;
 				int TI = Integer.parseInt(st.nextToken());
 				nodes[S].add(new int[] {E,TI});
 				nodes[E].add(new int[] {S,TI});
 				++j;
 			}
 			
 			for(int j=0;j<W;) {
 				st = new StringTokenizer(br.readLine());
 				int S = Integer.parseInt(st.nextToken())-1;
 				int E = Integer.parseInt(st.nextToken())-1;
 				int TI = Integer.parseInt(st.nextToken());
 				nodes[S].add(new int[] {E,-TI});
 				++j;
 			}
 			
 			boolean infinite = false;
 			ArrayDeque<Integer> dq = new ArrayDeque<>();
 			top:
 			for(int j=0;j<N;) {
 			    // 모든 노드를 시작점으로 SPFA를 실행하여 음수 사이클이 존재하는지 파악
 				
 			  	int cnt[] = new int[N];
 			  	int cost[] = new int[N];
 			  	Arrays.fill(cost, 987654321);
 			  	boolean InQ[] = new boolean[N];
 				
 				dq.add(j);
 				cnt[j]=1;
 				InQ[j]=true;
 				
 				while(!dq.isEmpty()) {
 					int now = dq.poll();
 					InQ[now] = false;
 					int size = nodes[now].size();
 					for(int k=0;k<size;) {

 						int next = nodes[now].get(k)[0];
 						int pathValue = nodes[now].get(k)[1];
 						if(cost[next] > cost[now] + pathValue) {
 							cost[next] = cost[now] + pathValue;
 							if(!InQ[next]) {
 								InQ[next] = true;
 								if(++cnt[next]>N) {
 									infinite=true;
 									break top;
 								}
 								dq.add(next);
 							}
 						}
 						k++;
 					}
 				}
 				++j;
 			}
 			if(infinite) {
 				sb.append("YES\n");
 			} else {
 				sb.append("NO\n");	
 			}
 			++i;
		}
		System.out.println(sb.toString());
		
	}

}

---