문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

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

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

풀이

다익스트라 알고리즘을 사용해서 풀어야 한다.

문제를 읽어보면 각 집에서 X집으로 갔다가 오는 왕복했을 때 걸리는 시간을 구해야 해서 플로이드 워셜 알고리즘을 생각했었다. 하지만 N의 크기가 1000이고 플로이드 워셜알고리즘의 시간복잡도가 $O(N^3)$이기 때문에 시간 초과가 무조건 발생한다.

처음 생각 했던 방식이 파티에 참석하러 가는 경우와, 파티가 끝나고 각자의 집으로 돌아오는 경우로 나누어 구하려고 했다.

두번째 경우는 시작점에서 각 점까지의 최단거리를 구하는 다익스트라 알고리즘을 사용할 수 있지만, 첫번째 경우는 여러개의 시작점에서 하나의 도착점으로 가는 최소 비용을 구해야하기 때문에 하나하나 다익스트라를 사용해야 했고, 결국 비효율적인 것임을 알게 되었다.

여러가지 고민 끝에 다른 사람의 풀이를 참고해서 풀게 되었다. (링크)

앞서 말한 두번째 경우는 다익스트라 사용해서 바로 구하면 되고 첫번째 경우에 대해서만 풀이함

첫번째 경우에 대해서 단방향으로 주어지는 길를 리스트에 그대로 넣는 것이 아니라 반대로 뒤집어서 넣는 것이다. 예를 들어, 1번 집에서 X(2번)번 집으로 가는 길이 4이면 X번 집에서 1번집으로 가능 길이 4로 넣는 것이다.

이와 같이 하는 이유는 시작점을 X번으로 고정시키기 위함이다. 그렇게 되면 다익스트라를 사용해서 X번에서 각각의 집까지의 최소비용을 구할 수 있게된다.

따라서 2가지 경우에 대해서 최소 거리비용을 저장하는 배열을 2개 만들어서 각각 다익스트라를 적용하고 그 뒤에 2개의 배열에서 인덱스가 맞는 것끼리 합한 후 제일 큰 값을 출력하면 된다.

소스

import java.util.*;

class Node implements Comparable<Node> {
	private int index;
	private int distance;

	public Node(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}

	public int getIndex() {
		return this.index;
	}

	public int getDistance() {
		return this.distance;
	}

	@Override
	public int compareTo(Node o) {
		if (this.distance < o.distance) {
			return -1;
		}
		return 1;
	}
}

public class Main {
	public static final int INF = (int) 1e9;
	public static int n, m, x;

	public static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	public static ArrayList<ArrayList<Node>> reverseGraph = new ArrayList<>();
	public static int[] d1 = new int[1001];
	public static int[] d2 = new int[1001];

	public static int[] dijkstra(ArrayList<ArrayList<Node>> g) {
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		int[] result = new int[1001];
		Arrays.fill(result, INF);

		pq.offer(new Node(x, 0));
		result[x] = 0;

		while (!pq.isEmpty()) {
			Node node = pq.poll();
			int dist = node.getDistance();
			int now = node.getIndex();

			if (result[now] < dist)
				continue;

			for (int i = 0; i < g.get(now).size(); i++) {
				int cost = result[now] + g.get(now).get(i).getDistance();

				if (cost < result[g.get(now).get(i).getIndex()]) {
					result[g.get(now).get(i).getIndex()] = cost;
					pq.offer(new Node(g.get(now).get(i).getIndex(), cost));
				}
			}
		}

		return result;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		x = sc.nextInt();

		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<Node>());
			reverseGraph.add(new ArrayList<Node>());
		}

		for (int i = 0; i < m; i++) {
			// a: 시작점 b : 도착점 c : 시간(비용)
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();

			graph.get(a).add(new Node(b, c));
			reverseGraph.get(b).add(new Node(a, c));
		}

		d1 = dijkstra(graph);
		d2 = dijkstra(reverseGraph);

		int ans = 0;
		for (int i = 1; i <= n; i++) {
			ans = Math.max(ans, d1[i] + d2[i]);
		}

		System.out.println(ans);

	}

}