[백준] 18223 민준이와마산그리고건우 [JAVA]

문제 링크 : https://www.acmicpc.net/problem/18223

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

민준이가 최단 경로로 갈 때, 그 경로에 건우가 있다면 SAVE HIM을 출력하는 문제다.

최단 경로이므로 다익스트라를 활용할 수 있을 것이라 생각했다.

문제에서 최단 경로가 여러개이고 그 경로들 중에 건우를 구할 수 있을 때, 민준이는 건우를 구하는 경로를 택한다 하였다. 따라서 X->Y로의 거리가 X->Z->Y의 거리가 같은 경우도 모두 탐색할 수 있도록 하면 최단 거리인 경로를 모두 탐색할 수 있다. 

import java.util.*;
import java.io.*;
public class Main {
    public static class Node{
        int num;
        int cost;
        boolean isSave;
        public Node(){}
        public Node(int a,int b){
            num = a;
            cost = b;
        }
        public Node(int a,int b, boolean c){
            num = a;
            cost = b;
            isSave = c;
        }
    }
    public static int V,E,P;
    public static int dist[];
    public static ArrayList<Node> adj[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());

        dist = new int[V+1];
        adj = new ArrayList[V+1];
        for(int i=1;i<=V;i++){
            adj[i] = new ArrayList<Node>();
            dist[i] = 987654321;
        }
        for(int i=0;i<E;i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            adj[s].add(new Node(e,c));
            adj[e].add(new Node(s,c));
        }
        dist[1] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<Node>((o1, o2) -> o1.cost-o2.cost);
        pq.offer(new Node(1,0));
        int endDist = 987654321;
        boolean success = false;
        while(!pq.isEmpty()){
            Node curNode = pq.poll();
            int curNum = curNode.num;
            int curCost = curNode.cost;
            boolean isSuc = curNode.isSave;
            if(curNum == V){
                if(curCost > endDist)
                    break;
                if(isSuc== true){
                    success = true;
                    break;
                }
                endDist = curCost;
            }
            boolean sucNext = isSuc;
            if(curNum==P){
                sucNext = true;
            }
            for(int i=0;i<adj[curNum].size();i++){
                Node nextNode = adj[curNum].get(i);
                int nextNum = nextNode.num;
                int nextCost = nextNode.cost;
                if(curCost + nextCost > dist[nextNum])continue;
                dist[nextNum] = curCost + nextCost;
                pq.offer(new Node(nextNum,curCost+nextCost,sucNext));
            }
        }
        if(success==true){
            System.out.println("SAVE HIM");
        }else{
            System.out.println("GOOD BYE");
        }
    }
}