[BOJ]1238号:チーム(JAVA)
3357 ワード
質問する (Gold 3)
1238番:チーム
に答える
Nから目的地Xまでの最短距離->A
目的地Xから村ごとNまでの最短距離->B
往復距離を求める最短距離を利用!
Bは複数のアルゴリズムを用いて始点から全ノードまでの距離を求める.
Aの場合,floydとshallを用いて全ノード間の距離を求めようとする.
しかし、フロイドとシャーロットにとってタイムアウトは失敗!
逆に考えてみると、
全ての経路を逆さに保存して、出発地Xから各村Nまでの最短距離を求めれば良いのです!!!
あ~(この部分を考えると結構時間がかかったなぁ)~
つまり、A、Bは基本的なドエストラで求めることができる簡単な問題です!
コード#コード#
package shortestPath;
import java.util.*;
import java.io.*;
public class BOJ_1238_파티 {
static int N,X;
static List<int[]>[] road;
static List<int[]>[] road_back;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken())-1;
road = new List[N]; // X에서 N 마을로 가는 경로 판별할 때
road_back = new List[N]; // N 마을들에서 X로 가는 경로 판별할 때
for(int i =0 ; i < N ; i++){
road[i] = new ArrayList<>();
road_back[i] = new ArrayList<>();
}
for(int i =0 ; i < M ; i++){
st = new StringTokenizer(br.readLine());
int to = Integer.parseInt(st.nextToken())-1;
int from = Integer.parseInt(st.nextToken())-1;
int time = Integer.parseInt(st.nextToken());
road[to].add(new int[]{from, time});
road_back[from].add(new int[]{to, time});
}
int[] XToN = getDist(road);
int[] NToX = getDist(road_back);
int max = 0;
for(int i =0 ; i < N ; i++){
max = Math.max(max, XToN[i]+NToX[i]);
}
System.out.println(max);
}
private static int[] getDist(List<int[]>[] road) {
int[] dist = new int[N];
Arrays.fill(dist, Integer.MAX_VALUE);
PriorityQueue<int[]> pq = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1[1], o2[1])));
boolean[] visited = new boolean[N];
pq.offer(new int[]{X, 0});
dist[X] = 0;
while(!pq.isEmpty()){
int[] cur = pq.poll();
if(visited[cur[0]]) continue; // 이미 경로 탐색이 되어있으면 확인할 필요 없음
visited[cur[0]] = true;
for(int[] r:road[cur[0]]){
if(dist[r[0]] > dist[cur[0]] + r[1]){ // 현재 노드를 들렸다 갈 때가 더 빠를 경우
dist[r[0]] = dist[cur[0]] + r[1];
pq.add(new int[]{r[0], dist[r[0]]});
}
}
}
return dist;
}
}
Reference
この問題について([BOJ]1238号:チーム(JAVA)), 我々は、より多くの情報をここで見つけました https://velog.io/@dot2__/BOJ-1238번-파티-JAVAテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol