링크

1238 파티

문제

풀이

이 문제를 봤을 때 플로이드 와샬로 풀었다.
그리고 다른사람 풀이를 보는데 다익스트라 알고리즘을 사용한다고 했다.

그래서 다익스트라를 공부했다...
다익스트라와 플로이드와샬은 비용의 최솟값을 찾는 알고리즘은 맞다. 그러나 플로이드 와샬은 모든 정점에 대한 모든 정점의 비용이지만 다익스트라는 한 정점에서 시작해서 모든 정점을 찾는 알고리즘이다

코드

다익스트라

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Node implements Comparable<Node>{
    int to;
    int value;

    public Node(int to, int value){
        this.to = to;
        this.value = value;
    }

    @Override
    public int compareTo(Node o){
        return this.value - o.value;
    }
}

public class Main {
    public static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");

        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);
        int x = Integer.parseInt(arr[2]);

        List<Node>[] listA = new ArrayList[n+1];
        List<Node>[] listB = new ArrayList[n+1];
        visited = new boolean[n+1];
        int[] dp1 = new int[n+1];
        int[] dp2 = new int[n+1];

        for(int i=0;i<listA.length;i++){
            listA[i] = new ArrayList<>();
            listB[i] = new ArrayList<>();
        }

        Arrays.fill(dp1, Integer.MAX_VALUE);

        for(int i=0;i<m;i++){
            arr = br.readLine().split(" ");

            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);
            int c = Integer.parseInt(arr[2]);

            listA[a].add(new Node(b, c));
            listB[b].add(new Node(a, c));
        }


        d(x, listA, dp1);
//        System.out.println(Arrays.toString(dp1));
        visited = new boolean[n+1];
        Arrays.fill(dp2, Integer.MAX_VALUE);
        d(x, listB, dp2);
//        System.out.println(Arrays.toString(dp2));

        int max = 0;
        for(int i=1;i<dp1.length;i++){
            max = Math.max(max, dp1[i] + dp2[i]);
        }

        System.out.println(max);


    }

    public static void d(int start, List<Node>[] list, int[] dp){
        Queue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dp[start] = 0;

        while(!pq.isEmpty()){
            Node node = pq.poll();
            int to = node.to;
            int value = node.value;

            if(visited[to]) continue;

            visited[to] = true;

            for(Node element : list[to]){
                if(dp[element.to] >= dp[to] + element.value){
                    dp[element.to] = dp[to] + element.value;
                    pq.add(new Node(element.to, dp[element.to]));
                }
            }


        }

    }

}

플로이드 와샬

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


//14889
public class Main {
    public static final int INF = 10000000;
    public static int[][] matrix = null;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");

        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);
        int x = Integer.parseInt(arr[2]);
        matrix = new int[n+1][n+1];

        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix.length;j++){
                if(i != j) matrix[i][j] = INF;
            }
        }

        for(int i=0;i<m;i++){
            arr = br.readLine().split(" ");

            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);
            int c = Integer.parseInt(arr[2]);

            matrix[a][b] = c;
        }

//        for(int i=0;i<matrix.length;i++){
//            System.out.println(Arrays.toString(matrix[i]));
//        }

        ployd(matrix);

//        System.out.println("-----------------------");
//
//        for(int i=0;i<matrix.length;i++){
//            System.out.println(Arrays.toString(matrix[i]));
//        }

        int max = 0;
        for(int i=1;i<matrix.length;i++){
            max = Math.max(max, matrix[i][x] + matrix[x][i]);
        }

        System.out.println(max);

    }

    public static void ployd(int[][] matrix){
        for(int k=1;k<matrix.length;k++){
            for(int i=1;i<matrix.length;i++){
                for(int j=1;j<matrix.length;j++){
                    matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
                }
            }
        }
    }

}