[BOJ] 18223. 민준이와 마산 그리고 건우

다익스트라를 활용한 문제였다.

총 2번의 다익스트라를 활용하였는데, 출발점 기준 그리고 친구 기준으로 두번 다익스트라를 활용하였다. 출발에서 목적지까지의 거리랑 출발에서 친구 + 친구에서 목적지 까지의 거리를 비교하는 간단한 문제였다.

package algostudy3;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_bj_18223_민준이와마산그리고건우 {
 
    static class Pos implements Comparable<Pos> {
        int point, weight;
 
        public Pos(int point, int weight) {
            this.point = point;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Pos o) {
            return Integer.compare(weight, o.weight);
        }
    }
 
    static int V;
    static int friend;
    static List<Pos>[] graph;
    static int[] d;
    static boolean[] visit;
 
    static PriorityQueue<Pos> pq;
 
    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());
        int E = Integer.parseInt(st.nextToken());
        friend = Integer.parseInt(st.nextToken());
 
        graph = new ArrayList[V + 1];
        d = new int[V + 1];
        visit = new boolean[V + 1];
 
        for (int i = 1; i <= V; i++) {
            graph[i] = new ArrayList<>();
            d[i] = Integer.MAX_VALUE / 2;
        }
 
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
 
            graph[a].add(new Pos(b, w));
            graph[b].add(new Pos(a, w));
 
        }
 
        dijkstra(1);
 
        int startToDestination = d[V];
        int startToFriend = d[friend];
 
        visit = new boolean[V + 1];
        d = new int[V + 1];
        for (int i = 1; i <= V; i++) {
            d[i] = Integer.MAX_VALUE / 2;
        }
 
        dijkstra(friend);
 
        int friendToDestination = d[V];
 
        if (startToDestination < startToFriend + friendToDestination) {
            System.out.println("GOOD BYE");
        } else {
            System.out.println("SAVE HIM");
        }
    }
 
    static void dijkstra(int start) {
        pq = new PriorityQueue<>();
        d[start] = 0; 
 
        pq.offer(new Pos(start, d[start]));
 
        while (!pq.isEmpty()) {
            Pos cur = pq.poll();
 
            if (visit[cur.point] == true) {
                continue;
            }
 
            for (Pos pos : graph[cur.point]) {
                int next = pos.point;
 
                if (visit[next] == false && d[next] > d[cur.point] + pos.weight) {
                    d[next] = d[cur.point] + pos.weight;
                    pq.offer(new Pos(next, d[next]));
                }
            }
 
            visit[cur.point] = true;
        }
    }
}