[BOJ/Gold 4] 백준 30974 What's your ETA?(C++)

문제 링크

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

30974번: What's your ETA?

 

문제

진주 나들이를 온 보선이는 버스를 타고 미리 예약해놓은 진양호 전망대에 가기 위해 가까운 버스 정류장에 도착했다. 그런데 이상하게 버스정보안내단말기에 단 한 대의 도착 정보도 표시되지 않았다. 당황한 보선이가 여기저기 알아보던 도중, 보선이의 대학 동기인 준희로부터 문자 한 통이 왔다.

맛이 어때?

 

알고 보니 이는 준희가 한 짓이었다. 대학생 때 국밥 마니아 보선이 때문에 매일 국밥만 먹게 되었던 리조또 마니아 준희는 지금까지 앙심을 품고 있었다. 마침 준희는 보선이가 진주에 놀러 왔다는 사실을 알게 되었고, 천재적인 해킹 실력을 발휘해 버스정보시스템을 해킹하여 시내버스가 다니지 못하게 만들었던 것이다.

하지만, 진주에는 Super Bus라는 재난 대비 버스가 있었다. 진주시는 버스정보시스템이 해킹된 지금의 상황이 사실상 재난에 준한다고 판단하여 Super Bus의 운행을 시작했다. 또한, Super Bus가 원활하게 운행되기 위해서 다른 교통수단은 전부 이용할 수 없게 되었다.

진주에는 버스 정류장이 N개가 있고 1번부터 차례대로 번호가 부여되어 있다. 그리고 서로 다른 두 버스 정류장 사이를 잇고 Super Bus를 타고 지나가는 데 소요되는 시간이 정해져 있는 M개의 양방향 도로가 있으며, 임의의 두 버스 정류장 사이에 도로가 두 개 이상 존재할 수 있다. 또한, 각 버스 정류장에는 5,000,000 이하의 양의 정수인 재난 코드가 부여되어 있으며, Super Bus는 재난 코드의 합이 소수인 두 버스 정류장 사이를 잇는 도로에서만 운행된다. 이 문제에서 소수란 1과 자기 자신 외의 약수를 갖지 않는 2 이상의 정수를 뜻한다.

보선이는 진주에서 많은 시간을 보냈기 때문에 N개의 버스 정류장의 재난 코드와 그 사이를 잇는 M개의 양방향 도로를 전부 꿰고 있다. 이 지식을 활용해 보선이는 진양호 전망대에 도착하는 시간을 미리 계산해 보고 예약 시간에 늦을 것 같으면 진양호 전망대에 전화를 걸어 그 사실을 알리고자 한다. 보선이가 출발하는 곳은 1번 버스 정류장이고 진양호 전망대가 있는 곳은 N번 버스 정류장이다. 또한, 모든 버스 정류장은 서로 먼 거리에 있기 때문에 Super Bus로만 이동이 가능하다. 그리고 버스 정류장에 도착하면 원하는 Super Bus를 바로 탈 수 있으며, 승하차에 필요한 시간은 없다고 가정하자. 이러한 조건하에 보선이가 진양호 전망대가 있는 N번 버스 정류장에 가장 빨리 도착할 때의 소요되는 시간을 알아보자.

 

입력

첫 번째 줄에는 버스 정류장의 개수 N과 임의의 두 버스 정류장 사이를 잇는 양방향 도로의 개수 M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 400,000; 1 ≤ M ≤ 1,000,000)

두 번째 줄에는 각 버스 정류장의 재난 코드 D1, …, DN이 공백으로 구분되어 주어진다. (1 ≤ Di ≤ 5,000,000)

세 번째 줄부터 M개의 줄에 걸쳐 각 양방향 도로의 정보 ui, vi, wi가 공백으로 구분되어 주어진다. 이는 ui번 버스 정류장과 vi번 버스 정류장 사이를 잇고 Super Bus를 타고 지나가는 데 소요되는 시간은 wi인 i번째 양방향 도로를 뜻한다. (1 ≤ ui < vi ≤ N; 1 ≤ wi ≤ 400,000) 

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

 

출력

첫 번째 줄에 '진양호 전망대'에 가장 빨리 도착할 때의 소요되는 시간을 출력한다. 만약 '진양호 전망대'에 도착하지 못한다면 Now where are you?를 출력한다.

 

예제 입력 1

5 5
1 1 5 1 1
1 2 2
1 3 1
2 4 2
3 5 1
4 5 2

예제 출력 1

6

예제 입력 2

5 5
1 1 5 5 1
1 2 2
1 3 1
2 4 2
3 5 1
4 5 2

예제 출력 2

Now where are you?

 

알고리즘 분류

• 최단 거리 알고리즘
• 소수 판정

 

풀이

재난 코드의 합의 최댓값은 10,000,000이므로, 2부터 10,000,000까지 소수인지 아닌지를 먼저 기록해둔다.

그리고 1번 정류장을 기준으로 2부터 N까지 각각의 정류장까지 도달하는 데 소요되는 최소의 시간을 데이크스트라를 사용하여 기록한다.

이 때, 출발하는 정류장과 도착하는 정류장의 재난 코드의 합이 소수인지 아닌지도 동시에 판별해야 한다.

마지막으로 N번 정류장까지 도달하는 데 소요되는 최소의 시간을 출력하며, N번 정류장까지 도달할 수 없다면 Now where are you?를 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <algorithm>
#define MAX 400001
#define MAX_D 10000001
#define INF 4e11
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
LL N, M, U, V, W;
LL D[MAX], Dist[MAX], DP[MAX_D];
vector<pair<LL, LL> > Edge[MAX];

void eratosthenes() {
    for (int i = 2; i < MAX_D; i++) {
        DP[i] = i;
    }
    for (int i = 2; i <= sqrt(MAX_D); i++) {
        if (DP[i] == 0) {
            continue;
        }
        for (int j = (i * i); j < MAX_D; j += i) {
            DP[j] = 0;
        }
    }
}

void input() {
    cin >> N >> M;
    for (LL i = 1; i <= N; i++) {
        cin >> D[i];
        Dist[i] = INF;
    }
    Dist[1] = 0;
    for (LL i = 0; i < M; i++) {
        cin >> U >> V >> W;
        Edge[U].push_back(make_pair(V, W));
        Edge[V].push_back(make_pair(U, W));
    }
}

void settings() {
    priority_queue<pair<LL, LL> > PQ;
    PQ.push(make_pair(0, 1));

    while (!PQ.empty()) {
        LL NowC = -PQ.top().first;
        LL NowX = PQ.top().second;
        PQ.pop();

        if (Dist[NowX] < NowC) {
            continue;
        }

        for (int i = 0; i < (int)Edge[NowX].size(); i++) {
            LL NextC = Edge[NowX][i].second;
            LL NextX = Edge[NowX][i].first;
            LL NowD = D[NowX] + D[NextX];
            if ((DP[NowD] != 0) && (Dist[NextX] > Dist[NowX] + NextC)) {
                Dist[NextX] = Dist[NowX] + NextC;
                PQ.push(make_pair(-Dist[NextX], NextX));
            }
        }
    };
}

void find_Answer() {
    if (Dist[N] == INF) {
        cout << "Now where are you?\n";
    }
    else {
        cout << Dist[N] << "\n";
    }
}

int main() {
    FASTIO
    eratosthenes();
    input();
    settings();
    find_Answer();

    return 0;
}