[1916] 최소비용 구하기

문제 링크 : https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

 

문제 해결 방법

다익스트라 알고리즘 이용했습니다.

 

ㅎㅎ,,

 

놓쳤던 부분

1. 1 3 4 / 1 3 6과 같이 출발지, 도착지는 같지만 비용이 다른 입력이 있을 수 있다.
2. 버스 비용은 0보다 크거나 같고 100,000보다 작은 정수이다. 👉 비용이 0인 입력이 있을 수 있다. (문제 제대로 읽자..)

1번을 위해 더 작은 비용의 경로를 저장했고, 2번을 위해 경로가 없다면 Integer.MAX_VALUE을 저장해서 맞출 수 있었습니다.

 

import java.util.Scanner;

public class Main {
    static int N, M, from, to;
    static int[] dist;
    static int[][] map;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N + 1][N + 1];
        dist = new int[N + 1];

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                map[i][j] = Integer.MAX_VALUE;
            }
        }

        for (int i = 0; i < M; i++) {
            int city1 = sc.nextInt();
            int city2 = sc.nextInt();
            int cost = sc.nextInt();
            if (map[city1][city2] == Integer.MAX_VALUE) {
                map[city1][city2] = cost;
            } else {
                if (map[city1][city2] > cost) { // 더 작은 비용 저장
                    map[city1][city2] = cost;
                }
            }
        }
        from = sc.nextInt();
        to = sc.nextInt();

        for (int i = 1; i < N + 1; i++) {
            dist[i] = map[from][i]; // 거리 배열 초기화
        }

        dijkstra();

        System.out.println(dist[to]);
    }

    private static void dijkstra() {
        boolean[] visit = new boolean[N + 1];
        visit[from] = true;

        for (int i = 0; i < N - 1; i++) {
            int min = Integer.MAX_VALUE;
            int idx = 0;

            for (int j = 1; j < N + 1; j++) { // 최단 거리 찾기
                if (!visit[j] && dist[j] < min) {
                    idx = j;
                    min = dist[j];
                }
            }

            visit[idx] = true; // 최단 거리 방문

            for (int j = 1; j < N + 1; j++) { // 경유해서 가는게 더 빠르다면 업데이트
                if (!visit[j] && map[idx][j] != Integer.MAX_VALUE && dist[idx] + map[idx][j] < dist[j]) {
                    dist[j] = dist[idx] + map[idx][j];
                }
            }
        }
    }
}