[BOJ1238] 파티

 

 

처음에는 단순히 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