✍ 문제
문제
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명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
👏 풀이과정
처음 플로이드 와샬로 진행하려고 하였지만 시간복잡도가 V^3이기 때문에 너무 길다고 생각하여 다익스트라로 바꾸었다. 아무 생각없이 모든 노드에 대해 X까지에 최소 거리를 다 구하였다가 시간초과로 틀렸다. 다른 게시글에 힌트를 얻어 ,단방향간선 이기 때문에 X 에서 역방향 간선으로 최솟값을 구하게 되면 모든 노드에서 X 까지에 최소 거리를 알 수 있다는 것을 깨달았다. 시작: X 간선: 역방향 간선, 시작: X : 원래 간선 두개의 합의 최대값을 구해주었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int[][] arr;
static int MAX = 1000001;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int X = Integer.parseInt(st.nextToken());
arr = new int[N+1][N+1];
for (int i = 0 ; i < M; i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
arr[x][y] = cost;
}
for (int i = 1 ; i < N+1; i++){
for(int j = 1 ; j < N+1 ; j++){
if (arr[i][j] == 0) {
arr[i][j] = MAX;
}
}
}
int[] arr_x = dijkstra(X, N);
int[] arr_x_reverse = dijkstra_reverse(X, N);
int max = 0;
for(int i = 1 ; i < N+1; i++){
max = Math.max(arr_x[i] + arr_x_reverse[i], max);
}
System.out.println(max);
}
static int[] dijkstra(int x,int N) {
int[] ar = new int[N + 1];
for (int i = 1 ; i < N+1; i++){
if (i != x) {
ar[i] = MAX;
}
}
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.add(new Node(x, 0));
while (!queue.isEmpty()) {
Node poll = queue.poll();
int x_x = poll.x;
if(poll.cost > ar[x_x]) continue;
for (int i = 1; i < N+1; i++){
if (arr[x_x][i] != MAX) {
if(ar[i] > poll.cost + arr[x_x][i]){
ar[i] = poll.cost + arr[x_x][i];
queue.add(new Node(i, ar[i]));
}
}
}
}
return ar;
}
static int[] dijkstra_reverse(int x,int N) {
int[] ar = new int[N + 1];
for (int i = 1 ; i < N+1; i++){
if (i != x) {
ar[i] = MAX;
}
}
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.add(new Node(x, 0));
while (!queue.isEmpty()) {
Node poll = queue.poll();
int x_x = poll.x;
if(poll.cost > ar[x_x]) continue;
for (int i = 1; i < N+1; i++){
if (arr[i][x_x] != MAX) {
if(ar[i] > poll.cost + arr[i][x_x]){
ar[i] = poll.cost + arr[i][x_x];
queue.add(new Node(i, ar[i]));
}
}
}
}
return ar;
}
static class Node implements Comparable<Node> {
int x;
int cost;
Node(int x, int cost) {
this.x = x;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return o.cost > cost ? 1: -1;
}
}
}
