처음에는 단순히 K번 노드에서 다른 노드까지의 최단 거리를 구해주면 되는 줄 알았다.
단방향 그래프이다보니 집에서 K번으로 가는 거리와 다르다는 것을 생각하지 못했다는 것을 푸는 도중에 알게되었다.
이럴 때는, 단방향 그래프를 반대로(s->e 였다면, e->s) 설정해주고 K번에서 역으로 되돌아가면 된다.
그래서 나는 인접그래프 2개와 거리배열 2개를 사용하기로 했다.
이후 dijkstra 메소드를 정의해주고, 2번 사용하는 방식으로 이 문제를 풀었다.
import java.io.*;
import java.util.*;
class BOJ1238 {
static class Node implements Comparable<Node>{
int idx, dist;
Node(int idx, int dist){
this.idx = idx;
this.dist = dist;
}
@Override
public int compareTo(Node n) {
return this.dist - n.dist;
}
}
static final int INF = (int)1e8;
static final int MN = 1005;
static final int MM = 10005;
static ArrayList<Node>[] graph = new ArrayList[MN];
static ArrayList<Node>[] regraph = new ArrayList[MN];
static PriorityQueue<Node> pq = new PriorityQueue<>();
static int dist[] = new int[MM];
static int redist[] = new int[MM];
static int N, M, K;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
for(int i=1; i<=N; ++i) {
graph[i] = new ArrayList<>();
regraph[i] = new ArrayList<>();
dist[i] = INF;
redist[i] = INF;
}
for(int i=0; i<M; ++i) {
st = new StringTokenizer(br.readLine(), " ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
graph[s].add(new Node(e, w));
regraph[e].add(new Node(s, w));
}
dist[K]=0;
redist[K]=0;
dist = dijkstra(dist, graph);
redist = dijkstra(redist, regraph);
int ans = 0;
for(int i=1; i<=N; ++i) {
ans = Math.max(ans, dist[i]+redist[i]);
}
sb.append(ans);
bw.write(sb.toString());
bw.close();
br.close();
}
static int[] dijkstra(int[] dist, ArrayList<Node>[] graph) {
pq.clear();
pq.add(new Node(K, dist[K]));
while(!pq.isEmpty()) {
Node cur = pq.poll();
int curIdx = cur.idx;
int curDst = cur.dist;
for(Node nx:graph[curIdx]) {
int nxIdx = nx.idx;
int nxDst = nx.dist;
int newDst = dist[curIdx] + nxDst;
if(dist[nxIdx] <= newDst) continue;
dist[nxIdx] = newDst;
pq.add(new Node(nxIdx, dist[nxIdx]));
}
}
return dist;
}
}
https://www.acmicpc.net/problem/1238
'코딩테스트(Coding Test) > 백준' 카테고리의 다른 글
[백준/BOJ16174] 점프왕 쩰리 (0) | 2024.07.06 |
---|---|
[백준/BOJ20002] 사과나무 (0) | 2024.07.04 |
[BOJ2011] 암호코드 (0) | 2024.02.01 |
[백준] 나머지와 몫이 같은 수 (0) | 2023.10.19 |
[백준/BOJ] 12865 평범한 배낭 (0) | 2023.08.16 |