[Java] 백준 1753번 최단경로 - 다익스트라

다익스트라의 구현

현재 O(n^2)이므로 O(nlgn)으로 다시 짤 것

내일 플로이드-와셜 알고리즘 공부할 것

package class4;

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

public class g5_1753{
    static int[] table;
    static List<Map<Integer, Integer>> map = new ArrayList<>();
    static boolean[] visit;
    public static void main(String[] args){
        FastScanner fs = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);

        int v = fs.nextInt(), e = fs.nextInt(), k = fs.nextInt() - 1;
        table = new int[v];
        visit = new boolean[v];
        Arrays.fill(table, Integer.MAX_VALUE);
        for (int i=0;i<v;i++) map.add(new HashMap<>());
        
        for (int i=0;i<e;i++){
            int a = fs.nextInt() - 1, b = fs.nextInt() - 1, dis = fs.nextInt();
            if (map.get(a).containsKey(b)){
                map.get(a).put(b, Math.min(map.get(a).get(b), dis));
            }
            else{
                map.get(a).put(b, dis);
            }
        }
        
        table[k] = 0;
        for (Integer i : map.get(k).keySet()){
            table[i] = map.get(k).get(i);
        }
        visit[k] = true;

        for (int i=0;i<v-1;i++){
            int next = nextNode();
            visit[next] = true;
            for (Integer j : map.get(next).keySet()){
                table[j] = Math.min(table[j], table[next] + map.get(next).get(j));
            }
        }

        for (Integer i : table){
            if (i == Integer.MAX_VALUE) pw.println("INF");
            else pw.println(i);
        }
        pw.close();
    }

    static int nextNode(){
        int dis = Integer.MAX_VALUE;
        int index = 0;
        for (int i=0;i<table.length;i++){
            if (table[i] < dis && !visit[i]){
                dis = table[i];
                index = i;
            }
        }
        return index;
    }

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