글 읽기 - 색다른 방식으로 풀었는데(이분탐색+bfs) 틀린 이유를 모르겠네요

tmfgh0719 3년 전 0

최단거리 알고리즘으로 푸는 법은 알고있는데 중량제한문제와 비슷하게 이분탐색+bfs로 풀어볼려니까 틀렸다고 나오네요..

반례가 무엇이 있는지 혹시 틀린부분을 알 수 있을까요?

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

public class B1916 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<ArrayList<City>> list = new ArrayList<ArrayList<City>>();
        for(int i=0; i<n; i++){
            list.add(new ArrayList<City>());
        }
        for(int i=0; i<m; i++){
            int idx = sc.nextInt()-1;
            list.get(idx).add(new City(sc.nextInt()-1, sc.nextInt()));
        }
        int start = sc.nextInt()-1;
        int end = sc.nextInt() -1;
        int low = 1;
        int high = Integer.MAX_VALUE;
        if(start != end){
            while (low<=high){
                int mid = (high+low)/2;
                if(bfs(list, new boolean[n], start, end, mid)){
                    high= mid-1;
                }else{
                    low = mid +1;
                }
            }
            System.out.println(low);
        }else{
            System.out.println(0);
        }
    }

    static boolean bfs(ArrayList<ArrayList<City>> list, boolean[] visited, int start, int end, int val){
        Queue<City> queue = new LinkedList<>();
        queue.offer(new City(start, 0));
        visited[start] =true;
        while (!queue.isEmpty()){
            City tmp = queue.poll();
            for(City c : list.get(tmp.goal)){
                if(val < c.cost + tmp.cost) continue;
                if(visited[c.goal]) continue;
                if(c.goal == end) return true;
                queue.offer(new City(c.goal, c.cost+tmp.cost));
                visited[c.goal] = true;
            }
        }
        return false;
    }
    static class City{
        int goal;
        int cost;

        City(int goal, int cost){
            this.goal = goal;
            this.cost = cost;
        }
    }
}

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

문제

문제

출처

ICPC

색다른 방식으로 풀었는데(이분탐색+bfs) 틀린 이유를 모르겠네요

tmfgh0719 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말