[BOJ/백준] 31230 - 모비스터디

31230번: 모비스터디

---

X는 최단경로에 있다 = (1-X 거리 + X-N 거리) 가 최단거리다

 

다익스트라에서 현재 위치의 거리를 최단거리로 만드려고 하는 CURR의 값이 최적이 아닌 경우

NEXT와 상관없이 최적이 될 수 없으므로 CONTINUE로 경우를 제외해야한다.

---

---

• 제목

모비스터디

---

• 조건

시간 제한 : 2 초

메모리 제한 : 1024 MB 

---

• 문제

현대모비스는 글로벌 자동차 부품 기업으로 자율주행, 커넥티비티, 전동화 분야에 역량을 집중해 스마트 모빌리티 시대를 선도하고 있습니다.

현대모비스는 앞으로 미래 모빌리티 산업에서 소프트웨어와 하드웨어를 결합한 차별화된 모빌리티 솔루션을 제공하는 선도기업으로 도약하기 위해 노력하고 있으며, 이러한 연구개발과 생산능력 등 핵심역량을 바탕으로 스마트 모빌리티, UAM, 로보틱스 사업분야로 비즈니스를 확대해 나가고 있습니다.

민겸이와 시은이는 이런 꿈의 직장인 현대모비스에 입사하기 위해 모비스터디라는 이름의 스터디를 진행하기로 했다. 하지만, 민겸이와 시은이는 서로 다른 도시에 살고 있기 때문에, 스터디를 진행할 장소를 정해야 한다.

민겸이와 시은이는 1번부터 N번까지 번호가 부여된 N개의 도시와 서로 다른 두 도시를 잇는 M개의 양방향 도로가 있는 나라에 살고 있다. 도로마다 통행하는 데 걸리는 시간이 양의 정수로 존재하고, 각 도시에서 도로를 통해 항상 다른 모든 도시로 이동할 수 있다. 또한, 같은 도시를 출발지와 도착지로 두고 있는 도로는 존재하지 않으며, 임의의 두 도시를 잇는 도로는 최대 1개 존재한다.

민겸이는 A번 도시, 시은이는 B번 도시에 살고 있다. 민겸이는 시은이와 모비스터디를 위해 둘이서 만날 도시를 정하려고 한다. 최단 경로 문제를 풀던 민겸이는 약속 장소를 정할 때, A 도시에서 B 도시까지 이동하는 최단 경로 위에 존재하는 도시로 약속 장소를 정하는 것이 좋다고 생각했다. 이때, 최단 경로가 여러 개라면 그중 하나 위에만 존재해도 된다. A번 도시와 B번 도시 또한 약속 장소가 될 수 있음에 유의하자.

하지만, 민겸이는 이러한 조건을 만족하는 도시가 어디 있는지 모른다. 민겸이는 이 문제를 풀기에는 너무 귀찮았기 때문에, 여러분에게 해결을 부탁했다.

---

• 입력

첫 번째 줄에 도시의 개수 N과 도로의 개수 M, 민겸이가 살고 있는 도시의 번호 A, 시은이가 살고 있는 도시의 번호 
B가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 200,000; 1 ≤ M ≤ 300,000; 1 ≤ A, B ≤ N; A ≠ B)

다음 M개에 줄에 각 도로의 정보를 나타내는 세 정수 a, b, c가 공백으로 구분되어 주어진다. 해당 도로는 a 도시와 b 도시를 양방향으로 잇고 있으며, 통행하는 데 c만큼의 시간이 걸린다. (1 ≤ a, b ≤ N; 1 ≤ c ≤ 10^9; a ≤ b) 

입력으로 주어지는 모든 수는 양의 정수다.

---

• 출력

첫째 줄에 민겸이가 약속 장소로 정할 수 있는 도시의 개수를 출력한다.

둘째 줄에 민겸이가 약속 장소로 정할 수 있는 도시의 번호를 공백으로 구분하여 오름차순으로 출력한다.

---

예제 입력1	예제 출력1
7 8 1 6 1 3 3 1 4 1 4 5 1 5 2 2 2 6 3 1 7 2 7 2 2 3 6 5	6 1 2 4 5 6 7

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static class NODE implements Comparable<NODE> {
        int index;
        long weight;

        public NODE(int index, long weight) {
            this.index = index;
            this.weight = weight;
        }

        @Override
        public int compareTo(NODE o) {
            return Long.compare(this.weight, o.weight);
        }
    }

    static void dijkstra(int STD, int S) {
        PriorityQueue<NODE> pq = new PriorityQueue<>();
        pq.add(new NODE(S, 0));
        distance[STD][S] = 0;

        while (!pq.isEmpty()) {
            NODE curr = pq.poll();
            if(distance[STD][curr.index] < curr.weight) continue;
            for (NODE next : edge[curr.index]) {
                if (distance[STD][next.index] <= distance[STD][curr.index] + next.weight) continue;
                distance[STD][next.index] = distance[STD][curr.index] + next.weight;
                pq.add(new NODE(next.index, distance[STD][next.index]));
            }
        }
    }

    static int N, M, A, B;
    static long[][] distance;
    static ArrayList<NODE>[] edge;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        distance = new long[2][N + 1];
        edge = new ArrayList[N + 1];

        for (int i = 0; i <= N; i++) {
            edge[i] = new ArrayList<>();
            distance[0][i] = Long.MAX_VALUE;
            distance[1][i] = Long.MAX_VALUE;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long w = Long.parseLong(st.nextToken());
            edge[a].add(new NODE(b, w));
            edge[b].add(new NODE(a, w));
        }

        dijkstra(0, A);
        dijkstra(1, B);

        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (distance[0][i] + distance[1][i] == distance[0][B]) {
                sb.append(i).append(" ");
                count++;
            }
        }
        System.out.println(count);
        System.out.println(sb);
    }
}