글 읽기 - 문제 조건 추가 요청

akswnd98 6년 전 0

아래의 소스코드로 AC판정을 받았습니다.

아래의 소스코드는 "모든 지점"들이 "시작 지점"인 "지점 1"로 가는 경로가 존재할 때 정상적으로 AC판정을 받을 수 있습니다.

가령 "지점 1"에서 "다른 지점"으로 가는 웜홀은 존재하지만 "다른 지점"에서 "지점 1"로 가는 웜홀이 없고 "지점 1"과 "다른 지점"을 연결하는 어떠한 도로도 없을 때의 경우를 다룬 "TEST CASE"는 AC판정을 받을 수 없습니다.

TEST CASE를 하나 예로 들어보겠습니다.

만약

1

5 1 4

1 2 1

1 3 0

3 4 1

4 5 1

5 3 1

과 같은 입력을 주었다면 정상적인 출력은 NO입니다. 하지만 위의 소스코드는 "지점 1"에서 시작하는 벨만-포드 알고리즘으로 단순히 음의 사이클을 발견했기 때문에 YES를 출력합니다.

즉 문제에 "모든 지점"들이 "시작 지점"인 "지점 1"로 가는 경로가 존재한다라는 조건을 추가하거나, 위의 예시와 같은 TEST CASE를 판정 머신에 추가하는 것이 좋을 것 같습니다.

import java.util.Scanner;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Iterator;

public class Main {
	public static class pair {
		public int dst;
		public int wth;
		
		pair(int dst, int wth) {
			this.dst = dst;
			this.wth = wth;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int C;
		int N, M, W;
		int S, E, T;
		int i, j, k;
		ArrayList<LinkedList<pair>> map;
		boolean[] flag;
		int count, next_count;
		int[] D;
		int cur;
		LinkedList<Integer> q;
		Iterator<pair> iter;
		pair next;
		
		C = sc.nextInt();
		flag = new boolean[C];
		for(i = 0; i < C; i++) {
			flag[i] = false;
		}
		for(i = 0; i < C; i++) {
			N = sc.nextInt();
			M = sc.nextInt();
			W = sc.nextInt();
			D = new int[N];
			for(j = 0; j < N; j++) {
				D[j] = Integer.MAX_VALUE;
			}
			map = new ArrayList<LinkedList<pair>>(N);
			for(j = 0; j < N; j++) {
				map.add(new LinkedList<pair>());
			}
			for(j = 0; j < M; j++) {
				S = sc.nextInt() - 1;
				E = sc.nextInt() - 1;
				T = sc.nextInt();
				map.get(S).offer(new pair(E, T));
				map.get(E).offer(new pair(S, T));
			}
			for(j = 0; j < W; j++) {
				map.get(sc.nextInt() - 1).offer(new pair(sc.nextInt() - 1, -sc.nextInt()));
			}
			
			q = new LinkedList<Integer>();
			q.offer(0);
			D[0] = 0;
			next_count = 1;
			for(j = 0; j < N - 1; j++) {
				count = next_count;
				next_count = 0;
				for(k = 0; k < count; k++) {
					cur = q.poll();
					iter = map.get(cur).iterator();
					while(iter.hasNext()) {
						next = iter.next();
						if(D[cur] + next.wth < D[next.dst]) {
							D[next.dst] = D[cur] + next.wth;
							q.offer(next.dst);
							next_count++;
						}
					}
				}
			}
			for(j = 0; j < next_count; j++) {
				cur = q.poll();
				iter = map.get(cur).iterator();
				while(iter.hasNext()) {
					next = iter.next();
					if(D[cur] + next.wth < D[next.dst]) {
						flag[i] = true;
						break;
					}
				}
				if(flag[i]) {
					break;
				}
			}
		}
		
		for(i = 0; i < C; i++) {
			if(flag[i]) {
				System.out.printf("YES\n");
			} else {
				System.out.printf("NO\n");
			}
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.