[Java] 백준 1865번 웜홀 - 벨만-포드 알고리즘

입력을 잘못받아 너무 고통스러운 문제...

다익스트라에서 나아간 알고리즘

 

1번 코드는 모든 노드에 대해 탐색하는 정석(오래걸리는) 알고리즘

2번 코드는 최악의 경우 n번 실행할 것을 O(1)에 끝내주는 문제 특화형 알고리즘

package class4;

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

public class g3_1865{
    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();
                if (!table.get(a).containsKey(b)){
                    table.get(a).put(b, wei);
                    table.get(b).put(a, wei);
                }
                else{
                    table.get(a).put(b, Math.min(wei, table.get(a).get(b)));
                    table.get(b).put(a, Math.min(wei, table.get(b).get(a)));
                }
            }
            for (int i=0;i<w;i++){
                int a = fs.nextInt(), b = fs.nextInt(), wei = fs.nextInt();
                if (!table.get(a).containsKey(b)){
                    table.get(a).put(b, -wei);
                }
                else{
                    table.get(a).put(b, Math.min(-wei, table.get(a).get(b)));
                }
            }

            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());
        }
    }
}

 

 

 

 

 

package class4;

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

public class g3_1865{
    static List<HashMap<Integer, Integer>> table;
    static int[] dist;
    static int INF = 999999999;
    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();
                if (!table.get(a).containsKey(b)){
                    table.get(a).put(b, wei);
                    table.get(b).put(a, wei);
                }
                else{
                    table.get(a).put(b, Math.min(wei, table.get(a).get(b)));
                    table.get(b).put(a, Math.min(wei, table.get(b).get(a)));
                }
            }
            for (int i=0;i<w;i++){
                int a = fs.nextInt(), b = fs.nextInt(), wei = fs.nextInt();
                if (!table.get(a).containsKey(b)){
                    table.get(a).put(b, -wei);
                }
                else{
                    table.get(a).put(b, Math.min(-wei, table.get(a).get(b)));
                }
            }

            if (bellman_ford()) pw.println("YES");
            else pw.println("NO");
        }

        pw.close();
    }

    static boolean bellman_ford(){
        dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        boolean update = false;
        for (int i=0;i<n-1;i++){
            update = false;
            for (int j=1;j<=n;j++){
                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++){
                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());
        }
    }
}