글 읽기 - 하 정말... 왜 틀리는건지..

filot 7년 전 0

예제는 잘 맞는데

올리기만 하면 틀리네요.

기존 로직은

1. 양방향 인접리스트 구성

2. 간선의 배열 별도 저장하고 해당 배열 오름차순 정렬

3. 이분검색 시작 : 시작 = 간선배열[1], 종료 = 간선배열[M]

4. BFS

입니다.

정말 어떤 예외를 생각을 못하는건지 도저히 모르겠는데

혹시나 조언을 부탁드리겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static int N;
	static int M;
	static int S;
	static int E;

	static List[] adjList;
	static int[] C;

	public static void main(String[] args) throws Exception {
		
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        StringTokenizer st = new StringTokenizer(reader.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        adjList = new List[N + 1];

        for (int i = 1; i <= N; i++)
        	adjList[i] = new ArrayList<Bridge>();

        C = new int[M + 1];

        for (int i = 1; i <= M; i++) {
        	st = new StringTokenizer(reader.readLine());

        	int u = Integer.parseInt(st.nextToken());
        	int v = Integer.parseInt(st.nextToken());
        	int c = Integer.parseInt(st.nextToken());

        	adjList[u].add(new Bridge(v, c));
        	adjList[v].add(new Bridge(u, c));
        	C[i] = c;
        }

        Arrays.sort(C);

        st = new StringTokenizer(reader.readLine());

        S = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        int begin = C[1];
        int end = C[M];     
        int result = 0;

        while (begin <= end) {
        	int middle = (begin + end) / 2;

        	if (bfs(middle)) {
        		result = middle;
        		begin = middle + 1;
        	}

        	else        		
        		end = middle - 1;
        }

        writer.println(result);

        writer.close();
        reader.close();
	}

	// maxC를 상한으로 bfs 수행이 가능한가?
	public static boolean bfs(int maxC) {
		boolean[] visited = new boolean[N + 1];
		Queue<Bridge> QUEUE = new ArrayDeque<Bridge>();

		visited[S] = true;
		QUEUE.offer(new Bridge(S, 0));

		while (!QUEUE.isEmpty()) {
			Bridge u = QUEUE.poll();

			if (u.v == E)
				return true;

			List<Bridge> list = adjList[u.v];

			for (Bridge v : list) {
				if (visited[v.v] && v.c > maxC)
					continue;

				visited[v.v] = true;
				QUEUE.offer(v);
			}
		}

		return false;
	}
}

class Bridge {
	int v;
	int c;

	public Bridge(int v, int c) {
		this.v = v;
		this.c = c;
	}
}

etaehyun4 7년 전 0

Line 101 이 잘못되었다는 느낌이 드네요

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

문제

문제

출처

ICPC

하 정말... 왜 틀리는건지..

filot 7년 전 0

etaehyun4 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말