기타

모각코_4회차

히어로맛쿠키 2024. 2. 14. 22:59

https://www.acmicpc.net/problem/1238

 

1238번: 파티

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어

www.acmicpc.net

 

문제 요약

 

플로이드와샬로 풀었다.

그치만 가중치 양수니까 다익스트라로 푸는게 시간적으로 좋겠으며, 다른 코드들을 보니까 그렇게들 많이 풀었다.

최단거리 알고리즘을 연습하기 좋은 문제였다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NMX = br.readLine().split(" ");
        int N = Integer.parseInt(NMX[0]);
        int M = Integer.parseInt(NMX[1]);
        int X = Integer.parseInt(NMX[2]);

        int[][] D1 = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    D1[i][j] = 0; continue;
                }
                D1[i][j] = Integer.MAX_VALUE;
            }
        }

        for (int i = 0; i < M; i++) {
            String[] line = br.readLine().split(" ");
            int start = Integer.parseInt(line[0]);
            int end = Integer.parseInt(line[1]);
            int time = Integer.parseInt(line[2]);
            D1[start][end] = time;
        }
        for (int n = 1; n <= N; n++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (D1[i][n] != Integer.MAX_VALUE && D1[n][j] != Integer.MAX_VALUE) {
                        if (D1[i][j] > D1[i][n] + D1[n][j]) {
                            D1[i][j] = D1[i][n] + D1[n][j];
                        }
                    }
                }
            }
        }
        for (int n = 1; n <= N; n++) {
            for (int i = 1; i <= N; i++) {
                if (D1[X][n] != Integer.MAX_VALUE && D1[n][i] != Integer.MAX_VALUE){
                    if (D1[X][i] > D1[X][n] + D1[n][i]) {
                        D1[X][i] = D1[X][n] + D1[n][i];
                    }
                }
            }
        }
        
        int longest = -1;
        for (int i = 1; i <= N; i++) {
            if (D1[i][X] == Integer.MAX_VALUE || D1[X][i] == Integer.MAX_VALUE) continue;
            if (longest < D1[i][X] + D1[X][i])
                longest = D1[i][X] + D1[X][i];
        }
        System.out.println(longest);
    }
}

 

(감사합니다^- ^ yes.. you..)

 

반응형