백준 18223번: 민준이와 마산 그리고 건우 Java 다익스트라

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

18223번: 민준이와 마산 그리고 건우

import java.util.*;

class Edge implements Comparable<Edge>{
    int x, c;
    Edge(int x, int c){
        this.x = x;
        this.c = c;
    }

    public int compareTo(Edge e){
        return c - e.c;
    }
}

public class Main {

    static int v, e, p;
    static ArrayList<Edge> adj[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        v = sc.nextInt();
        e = sc.nextInt();
        p = sc.nextInt();

        adj = new ArrayList[v+1];
        for(int i=0; i<=v; i++){
            adj[i] = new ArrayList<>();
        }


        for(int i=0; i<e; i++){
            int a,b,c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();

            adj[a].add(new Edge(b,c));
            adj[b].add(new Edge(a,c));
        }

        if(dikstra(1,v)==dikstra(1,p) + dikstra(p,v)){
            System.out.println("SAVE HIM");
        }
        else System.out.println("GOOD BYE");

    }

    static int dikstra(int st, int en){
        if(st==en) return 0;

        PriorityQueue<Edge> Q = new PriorityQueue<>();
        int dist[] = new int[v+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        Q.add(new Edge(st,0));

        while(!Q.isEmpty()){
            Edge cur = Q.poll();

            for(Edge nx : adj[cur.x]){
                if(dist[nx.x] > cur.c + nx.c){
                    dist[nx.x] = cur.c + nx.c;
                    Q.add(new Edge(nx.x, cur.c+nx.c));
                }
            }
        }

        return dist[en];
    }
}