글 읽기 - 41%에서 틀립니다.

ybc125 1년 전 0

간선 정보 넣어두고 distance 배열에 가장 distance 낮은 걸로 유지해준다음

싸이클이 음수인지 판단해서 정답 출력하는 건데 자꾸 41%에서 틀리네요...

반례 찾아주실 용자분 구합니다!

package 그래프_DFS;

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

public class Boj_1865_웜홀 {
	static boolean visited[][], chk;
	static List[] vertex;
	static int distance[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int TC = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < TC; i++) {
			StringTokenizer stz = new StringTokenizer(br.readLine());
			// 입력
			int N = Integer.parseInt(stz.nextToken());
			int M = Integer.parseInt(stz.nextToken());
			int W = Integer.parseInt(stz.nextToken());
			chk = false;
			vertex = new ArrayList[N+1];
			distance = new int[N+1][N+1];
			for (int j = 1; j <= N; j++) {
				vertex[j] = new ArrayList<Integer>();
				Arrays.fill(distance[j], 100000);
			}
			
			// vertex 입력 - 도로 무향, 웜홀 유향
			for (int j = 0; j < M; j++) {
				stz = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(stz.nextToken());
				int to = Integer.parseInt(stz.nextToken());
				int dist = Integer.parseInt(stz.nextToken());
				if(!vertex[from].contains(to)) {
					vertex[from].add(to);
					vertex[to].add(from);
				}
				distance[from][to] = Math.min(distance[from][to], dist);
				distance[to][from] = Math.min(distance[to][from], dist);
			}
			
			int hole[] = new int[W];
			int totalHoleDist = 0;
			for (int j = 0; j < W; j++) {
				stz = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(stz.nextToken());
				hole[j] = from;
				int to = Integer.parseInt(stz.nextToken());
				int dist = Integer.parseInt(stz.nextToken());
				totalHoleDist += dist;
				if(!vertex[from].contains(to)) {
					vertex[from].add(to);
				}
				distance[from][to] = Math.min(distance[from][to], -1*dist);
				
			}
			
			//dfs 처리 ( visited 배열로 재방문 안하게 하기 && 출발지점을 웜홀출발지점으로 돌리기 && 총 웜홀 거리 보다 크면 프루닝)
			
			for (int j = 1; j <= N; j++) {
//				System.out.println("start from :" + j);
				dfs(0, j, 0, j, totalHoleDist);
				if(chk) break;
			}
			
			if(chk) {
				sb.append("YES\n");
			}else {
				sb.append("NO\n");
			}
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb.toString());
	}

	private static void dfs(int prv, int cur, int totalDist, int start, int tempTotalHoleDist) {

		if(totalDist >= tempTotalHoleDist)return; // 프루닝
		
		if(chk)return; // 프루닝
		
		List<Integer> temp = vertex[cur];
		
		for (int i = 0; i < temp.size(); i++) {
			// 복귀 체크
			if(temp.get(i) == start && totalDist + distance[cur][temp.get(i)] < 0) {
				chk = true;
			}else if(temp.get(i) == start && totalDist + distance[cur][temp.get(i)] >= 0) {
				continue;
			}
			// 이전에 왔던 곳인지 체크
			if(temp.get(i) == prv) continue;
			 totalDist += distance[cur][temp.get(i)];
			 tempTotalHoleDist = distance[cur][temp.get(i)]<0 ? tempTotalHoleDist + distance[cur][temp.get(i)] : tempTotalHoleDist;
//			 System.out.println("from : " +cur + ", to: " + temp.get(i) +", " + distance[cur][temp.get(i)] +", totalDist :" + totalDist);
			dfs(cur, temp.get(i), totalDist, start, tempTotalHoleDist );
		}
	}
}

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

문제

문제

출처

ICPC

41%에서 틀립니다.

ybc125 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말