백준 21940번
https://www.acmicpc.net/problem/21940

문제

---

생각하기

---

• 최단 거리 구하기 문제입니다.

• 플로이드 워셜을 사용하여 풀었습니다.

동작

플로이드 워셜을 통해서 각 노드별 최단 거리를 구한다.

그 후 friends에서 각 노드별 총 합을 구해서 최소값으로 리스트를 만들면 된다.

        floyd();
        int ans = INF;
        List<Integer> list = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            int result = 0;
            for (int f : friends) {
                result = Math.max(result, arr[f][i] + arr[i][f]);
            }

            if (ans > result) {
                list = new ArrayList<>();
                list.add(i);
                ans = result;
            } else if (ans == result) {
                list.add(i);
            }
        }

플로이드 워셜이 더 좋은 이유

• 모든 노드 쌍 간의 최단 경로를 구해야 함

  • 다익스트라는 단일 출발점 최단 경로 알고리즘으로, 각 노드마다 다익스트라를 반복 수행해야 합니다.
  • 플로이드 워셜은 한 번으로 모든 쌍간의 최단 경로를 구할 수 있다.

• 시간 복잡도

  • 다익스트라 ${O(NlogN + E)}$
  • 플로이드 ${O(N^3)}$
  • $N = 200$

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M, K;
    private static int[][] arr;
    private static int[] friends;
    private static final int INF = Integer.MAX_VALUE / 2;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        floyd();
        int ans = INF;
        List<Integer> list = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            int result = 0;
            for (int f : friends) {
                result = Math.max(result, arr[f][i] + arr[i][f]);
            }

            if (ans > result) {
                list = new ArrayList<>();
                list.add(i);
                ans = result;
            } else if (ans == result) {
                list.add(i);
            }
        }

        Collections.sort(list);
        for (int idx : list) {
            sb.append(idx).append(' ');
        }

        return sb.toString();
    } // End of solve()

    private static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i == j) continue;

                    if (arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }
    } // End of floyd()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(arr[i], INF);
            arr[i][i] = 0;
        }

        for (int j = 0; j < M; j++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            arr[a][b] = t;
        }

        K = Integer.parseInt(br.readLine());
        friends = new int[K];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            friends[i] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class

import java.util.PriorityQueue
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var M = 0
private var K = 0

private const val INF = Int.MAX_VALUE / 2
private lateinit var times: Array<IntArray>
private lateinit var adjList: MutableList<MutableList<Edge>>
private lateinit var friends: IntArray

private data class Edge(var num: Int = 0, var time: Int = 0) : Comparable<Edge> {

    override fun compareTo(o: Edge): Int {
        return time - o.time
    }
}

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    for (i in 1..N) {
        dijkstra(i, times[i])
    }

    val list = ArrayList<Int>()
    var ans = INF
    for (i in 1..N) {
        var sum = 0
        var flag = true
        for (num in friends) {
            if (times[num][i] == INF || times[i][num] == INF) {
                flag = false
                break
            }
            sum = Math.max(sum, times[num][i] + times[i][num])
        }

        if (flag) {
            if (ans > sum) {
                ans = sum
                list.clear()
                list.add(i)
            } else if (ans == sum) {
                list.add(i)
            }
        }
    }

    list.sort()
    list.forEach {
        sb.append(it).append(' ')
    }

    return sb.toString()
} // End of solve()

private fun dijkstra(start: Int, times: IntArray) {
    val pque = PriorityQueue<Edge>()

    pque.offer(Edge(start, 0))
    times[start] = 0

    while (pque.isNotEmpty()) {
        val cur = pque.poll()

        if (cur.time > times[cur.num]) continue

        for (next in adjList[cur.num]) {
            if (times[next.num] > cur.time + next.time) {
                times[next.num] = cur.time + next.time
                pque.offer(Edge(next.num, times[next.num]))
            }
        }
    }
} // End of dijkstra()

private fun input() {
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    adjList = ArrayList()
    repeat(N + 1) {
        adjList.add(ArrayList())
    }
    times = Array(N + 1) { IntArray(N + 1) { INF } }

    repeat(M) {
        st = StringTokenizer(br.readLine())
        val a = st.nextToken().toInt()
        val b = st.nextToken().toInt()
        val t = st.nextToken().toInt()
        adjList[a].add(Edge(b, t))
    }

    K = br.readLine().toInt()
    st = StringTokenizer(br.readLine())
    friends = IntArray(K) {
        st.nextToken().toInt()
    }
} // End of input()