글 읽기 - java 반례 질문입니다...!

eksrks0310 2년 전 0

질문게시판에 있는 반례들을 모두 대입해봐도 반례를 도저히 찾지 못해 질문드립니다...ㅠㅠ (76퍼)

각 정점이 연결되는 정점과 가중치에 대한 정보는 table에 담아놓았고

어느 정점을 출발점으로 잡았을 때 n-1번 만큼 출발점에서의 거리인 dist를 갱신하고

한 번 더 갱신했을때 업데이트된다면 음수 사이클이 있다는 뜻이므로 yes를 출력하였습니다.

골드의 길은 참 험난하다는 걸 뼈저리게 느끼는 중입니다...

import java.util.*;
import java.io.*;

public class Main{
    static List<HashMap<Integer, Integer>> table;
    static int[] dist;
    static int INF = Integer.MAX_VALUE;
    static int n, m, w;
    public static void main(String[] args){
        FastScanner fs = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);

        int tc = fs.nextInt();
        for (int tt=0;tt<tc;tt++){
            n = fs.nextInt();
            m = fs.nextInt();
            w = fs.nextInt();
            table = new ArrayList<>();
            for (int i=0;i<=n;i++) table.add(new HashMap<>());
            for (int i=0;i<m;i++){
                int a = fs.nextInt(), b = fs.nextInt(), wei = fs.nextInt();
                table.get(a).put(b, wei);
                table.get(b).put(a, wei);
            }
            for (int i=0;i<w;i++){
                int a = fs.nextInt(), b = fs.nextInt(), wei = fs.nextInt();
                table.get(a).put(b, -wei);
            }

            boolean isCycle = false;
            dist = new int[n + 1];
            for (int i=1;i<=n;i++){
                if (bellman_ford(i)){
                    isCycle = true;
                    pw.println("YES");
                    break;
                }
            }
            if (!isCycle) pw.println("NO");
        }

        pw.close();
    }

    static boolean bellman_ford(int node){
        Arrays.fill(dist, INF);
        dist[node] = 0;
        boolean update = false;
        for (int i=0;i<n-1;i++){
            update = false;
            for (int j=1;j<=n;j++){
                if (dist[j] == INF) continue;
                for (Integer k : table.get(j).keySet()){
                    if (dist[j] + table.get(j).get(k) < dist[k]){
                        dist[k] = dist[j] + table.get(j).get(k);
                        update = true;
                    }
                }
            }
            if (!update) break;
        }

        if (update){
            for (int j=1;j<=n;j++){
                if (dist[j] == INF) continue;
                for (Integer k : table.get(j).keySet()){
                    if (dist[j] + table.get(j).get(k) < dist[k]){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

eksrks0310 2년 전 3

어이없는 곳에서 틀린걸 찾았습니다;;

처음에 table에 정점끼리의 관계를 기록할 때

3 4 2

3 4 3

이렇게 들어오면 길이가 더 긴 것으로 갱신되어버려서

만약 keySet에 다음 정점이 있다면 가중치가 더 작은 것을 기록하는 것으로 고쳤더니 성공했습니다

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

문제

문제

출처

ICPC

java 반례 질문입니다...!

eksrks0310 2년 전 0

eksrks0310 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말