N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
import java.io.*;
import java.util.*;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//N, M, X 입력 받기
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken())-1;
//배열 그래프 초기화
int[][] graph=new int[n][n];
for(int i=0; i<n; i++) {
Arrays.fill(graph[i], 100000000);
graph[i][i]=0;
}
//도로 정보 입력 받기
for(int i=0; i<m; i++){
st = new StringTokenizer(br.readLine());
graph[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = Integer.parseInt(st.nextToken());
}
//{방문 노드, Flag, 현재까지 비용}에서 비용을 기준으로 하는 우선순위큐
PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(o->o[2]));
//X 마을에서 각 마을까지로 갈 때(0), 올 때(1) 거리 초기화
//distance[1][1] = 1번 마을에서 X 마을로 올 때의 최소 거리
//distance[4][0] = X 마을에서 4번 마을로 갈 때의 최소 거리
int[][] distance=new int[n][2];
distance[x][0]=0;
distance[x][1]=0;
for(int i=0; i<n; i++) {
distance[i][0] = graph[x][i];
distance[i][1] =graph[i][x];
if(distance[i][0]!=100000000)
pq.add(new int[]{i, 0, distance[i][0]});
if(distance[i][1]!=100000000)
pq.add(new int[]{i, 1, distance[i][1]});
}
//방문 정보도 갈 때, 올 때로 나눠서 2차원 배열
boolean[][] visited=new boolean[n][2];
while(!pq.isEmpty()){
int[] ptr = pq.poll();
//방문 노드, 갈 때인지 올 때인지 Flag에 대해서 방문 검사
if(visited[ptr[0]][ptr[1]])
continue;
visited[ptr[0]][ptr[1]]=true;
for(int i=0; i<n; i++){
//i번 마을을 갈 때 또는 올 때 방문했으면 continue
if(visited[i][ptr[1]])
continue;
//X 마을에서 갈 때라면
if(ptr[1]==0)
//graph[현재 마을][i마을]로 최소 거리 갱신
if(distance[i][0]>ptr[2]+graph[ptr[0]][i]){
distance[i][0]=ptr[2]+graph[ptr[0]][i];
pq.add(new int[]{i, 0, distance[i][0]});
}
//X 마을로 올 때라면
if(ptr[1]==1)
//graph[i마을][현재 마을]로 최소 거리 갱신
if(distance[i][1]>ptr[2]+graph[i][ptr[0]]){
distance[i][1]=ptr[2]+graph[i][ptr[0]];
pq.add(new int[]{i, 1, distance[i][1]});
}
}
}
int answer=IntStream.range(0, n)
.map(o->distance[o][0]+distance[o][1])
.max()
.getAsInt();
System.out.println(answer);
}
}
Floyd로 푼다면 O(N^3)이 걸리게 된다. 이 문제는 모든 노드에서 X 노드로 가는 최소 거리 + X 노드에서 모든 노드로 가는 최소 거리를 구하는 것이다. 모든 노드에서 X 노드로 가는 최소 거리는 X 노드에서 출발해서 역방향 거리 정보를 가지고 Dijkstra를 하면 되고, X 노드에서 모든 노드로 가는 최소 거리는 X 노드에서 출발해서 정방향 거리 정보를 가지고 Dijkstra를 하면 된다.
이렇게 한다면 O(N^2)으로 가능하다.
😁