BOJ 5944 Apple Delivery Java

 

import java.io.*;
import java.util.*;

public class Main {
	static class Node implements Comparable<Node> {
		int index;
		long cost;
		
		public Node(int index, long cost) {
			this.index = index;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Node o) {
			return Long.compare(this.cost, o.cost);
		}
	}
	static int C, P, PB, PA1, PA2;
	static ArrayList<Node>[] graph;
	
	public static long dijkstra(int start, int end) {
		final long INF = Long.MAX_VALUE;
		long[] dist = new long[P+1];
		boolean[] check = new boolean[P+1];
		
		Arrays.fill(dist, INF);
		Arrays.fill(check, false);
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0));
		dist[start] = 0;
		
		while(!pq.isEmpty()) {
			Node now = pq.poll();
			
			if (now.index == end) {
				return now.cost;
			}
			
			if (check[now.index]) {
				continue;
			}
			check[now.index] = true;
			
			for (Node next : graph[now.index]) {
				long tmp_cost = now.cost + next.cost;
				if (dist[next.index] > tmp_cost) {
					pq.offer(new Node(next.index, tmp_cost));
					dist[next.index] = tmp_cost;
				}
			}
		}
		
		return INF;
	}
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		P = Integer.parseInt(st.nextToken());
		PB = Integer.parseInt(st.nextToken());
		PA1 = Integer.parseInt(st.nextToken());
		PA2 = Integer.parseInt(st.nextToken());
		
		graph = new ArrayList[P+1];
		for (int i=1; i<=P; i++) {
			graph[i] = new ArrayList<>();
		}
		
		for (int i=0; i<C; i++) {
			st = new StringTokenizer(br.readLine());
			int p1 = Integer.parseInt(st.nextToken());
			int p2 = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			graph[p1].add(new Node(p2, d));
			graph[p2].add(new Node(p1, d));
		}
		
		long result = Math.min(dijkstra(PB, PA1)+dijkstra(PA1, PA2), dijkstra(PB, PA2) + dijkstra(PA2, PA1));
		System.out.println(result);
	}
}

 

 

https://www.acmicpc.net/problem/5944

5944번: Apple Delivery