[BOJ] 백준 1238 파티

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

 Input 

4 8 2

1 2 4

1 3 2

1 4 7

2 1 1

2 3 5

3 1 2

3 4 4

4 2 3

 

 Output 

10

다른 정점들로부터 특정 정점까지의 최단 거리 비용을 구해야 하므로

플로이드 와샬 (Floyd Warshall)

플로이드 와샬 (Floyd Warshall)

 

 

같은 내용의 문제이지만, 다익스트라 알고리즘을 이용해서 풀이 

[SWEA] 4007 간담회 참석

[SWEA] 4007 간담회 참석

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
  
public class Main {
    public static final int INF = 1000000;
    public static int N, M, X;
    public static int[][] dist;
      
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine()); 
        N = Integer.parseInt(st.nextToken());
        dist = new int[N + 1][N + 1];
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(i == j) continue;
                dist[i][j] = INF;
            }
        }
          
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            dist[u][v] = cost;
        }
          
        // 플로이드 와샬 알고리즘
        floydWarshall();
          
        // 정답출력
        printAnswer();
    }
      
    public static void floydWarshall() {
        // 중간에 거쳐가는 정점 (k)
        for(int k = 1; k <= N; k++) {
            // 출발 정점 (i)
            for(int i=1; i <= N; i++) {
                // 도착 정점 (j)
                for(int j=1; j <= N; j++) {
                    // 기존에 저장된 최단 거리와 정점 k를 거쳐가는 (i → k) + (k → j) 경로 중 최소값
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
      
    public static void printAnswer() {
        StringBuilder sb = new StringBuilder();
        int answer = 0;
        for(int i=1; i <= N; i++) {
            if(i == X) continue;
            answer = Math.max(answer, dist[i][X] + dist[X][i]);
        }
        sb.append(answer);
        System.out.println(sb.toString());
    }
}