[BOJ/Gold 3] 백준 25636 소방차(C++)

문제 링크

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

25636번: 소방차

 

문제

ANA 도시는 N개의 교차로와, M개의 양방향 도로로 이루어져 있고, 교차로는 1번부터 N번까지 번호가 매겨져 있다. S번 교차로에는 ANA 도시의 유일한 소방서가 위치하는데, 무겸이는 이곳에서 소방차 운전 기사로 일하고 있다. 무겸이는 소방차를 타고 화재가 발생한 교차로에 출동해서 화재를 진압한다.

소방차에는 물을 담을 수 있는 물탱크가 있어서 이곳에 담은 물을 화재를 진압하는데에 사용할 수 있다. 소방차는 소방서에서 물탱크가 빈 상태로 출동하지만, 이동 중에 교차로에 도착할 때마다 교차로에 설치된 소화전을 이용해서 물탱크에 물을 충전한다. 소방차가 i번째 교차로에 한 번 도착할 때마다 충전하는 물의 양은 ai리터이며, 소방차는 소방서가 위치한 교차로에서 출동할 때나 화재가 발생한 교차로에 도착했을 때에도 물탱크에 물을 충전한다. 무겸이가 교차로에서 물을 충전하는데에는 시간이 걸리지 않고, 소방차의 물탱크의 용량에도 제한이 없다.

어느 날, T번 교차로에 화재가 발생했다. 무겸이는 소방차를 타고 화재가 발생한 교차로까지 최단 경로로 이동한다. 그런데 이러한 최단 경로는 여러 개가 있을 수 있다. 무겸이는 여러 개의 최단 경로 중에서 최대한 많은 양의 물을 가지고 도착할 수 있는 경로로 이동한다. 무겸이가 T번 교차로에 도착했을 때, 소방차의 이동 거리와 물탱크에 충전된 물의 양은 얼마일까?

입력

첫째 줄에 ANA 도시의 교차로의 개수를 의미하는 N(2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에 정수 a1, a2, ..., aN이 주어진다. ai(1 ≤ ai ≤ 1,000,000)는 소방차가 교차로에 한 번 도착할 때마다 충전하는 물의 양(리터)이다.

셋째 줄에 ANA 도시의 양방향 도로의 개수를 의미하는 M(1 ≤ M ≤ 300,000)이 주어진다.

넷째 줄부터 M개의 줄에 양방향 도로가 연결하는 양 끝 교차로의 번호 u, v(1 ≤ u, v ≤ N, u ≠ v)와 도로의 길이를 의미하는 정수 w(1 ≤ w ≤ 1,000,000)가 주어진다.

 M + 4번째 줄에 소방서가 위치한 교차로의 번호와 화재가 발생한 교차로의 번호를 의미하는 S, T(1 ≤ S, T ≤ N, S ≠ T)가 주어진다.

출력

 S번 교차로에서 T번 교차로까지 최단 경로의 길이를 출력한다. 그리고 최단 경로 중에서 최대한 많은 양의 물을 가지고 도착할 수 있는 경로로 이동했을 때 물탱크에 충전된 물의 양(리터)을 출력한다.

만약 소방차가 T번 교차로에 도착할 수 없다면 -1만을 출력한다.

예제 입력 1

8
7 2 4 5 5 1 1 3
10
1 2 1
1 3 2
1 4 1
2 5 3
2 6 3
3 6 2
4 7 4
5 8 1
6 8 1
7 8 3
1 8

예제 출력 1

5 17

 1 → 2 → 5 → 8순으로 교차로를 방문하면 경로의 길이는 5(1 + 3 + 1), 물탱크에 충전된 물의 양은 17(7 + 2 + 5 + 3)리터가 된다.

예제 입력 2

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

예제 출력 2

-1

알고리즘 분류

• 최단 거리 알고리즘

풀이

우선순위 큐를 사용한 데이크스트라 알고리즘을 통해 해결하며, 필요한 정보는 이동 거리, 교차로의 번호, 물의 양이다.

이 정보를 담기 위해 먼저 INFO 구조체를 선언해주고, INFO의 우선 순위를 재정의할 또 다른 구조체 COMPARE을 선언해 operator를 이동 거리가 가장 적은 원소가, 이동 거리가 같으면 물의 양이 가장 많은 원소가 더 높은 우선 순위를 가지도록 재정의한다.

이제 데이크스트라 알고리즘을 사용하여 소방서부터 각 교차로까지 도달하는 데 걸리는 최소의 이동 거리와 최대 물의 양을 기록하고, 마지막으로 T번 교차로까지 이동하는 데 필요한 최소 이동 거리와 최대 물의 양을 공백으로 구분하여 출력한다.

만약 T번 교차로까지 이동하는 데 필요한 최소 이동 거리가 INF라면 T번 교차로까지 도달할 수 없다는 뜻이므로 -1을 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 100001
#define INF 1e12
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct INFO {
    LL Cost, X, Water;
};

struct COMPARE {
    bool operator()(INFO& A, INFO& B) {
        if (A.Cost == B.Cost) {
            return (A.Water < B.Water);
        }
        return (A.Cost > B.Cost);
    }
};

LL N, M, U, V, W, S, T;
LL A[MAX];
vector<pair<LL, LL> > Edge[MAX];
pair<LL, LL> Dist[MAX];

void init() {
    for (LL i = 0; i < MAX; i++) {
        Dist[i].first = INF;
    }
}

void input() {
    cin >> N;
    for (LL i = 1; i <= N; i++) {
        cin >> A[i];
    }
    cin >> M;
    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));
    }
    cin >> S >> T;
}

void dijkstra() {
    priority_queue<INFO, vector<INFO>, COMPARE> PQ;
    PQ.push({ 0,S,A[S] });

    while (!PQ.empty()) {
        LL NowC = PQ.top().Cost;
        LL NowX = PQ.top().X;
        LL NowW = PQ.top().Water;
        PQ.pop();

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

        for (LL i = 0; i < Edge[NowX].size(); i++) {
            LL NextX = Edge[NowX][i].first;
            LL NextC = Edge[NowX][i].second;
            if (Dist[NextX].first > NowC + NextC) {
                Dist[NextX] = make_pair(NowC + NextC, NowW + A[NextX]);
                PQ.push({ Dist[NextX].first,NextX,NowW + A[NextX] });
            }
            else if (Dist[NextX].first == NowC + NextC) {
                if (Dist[NextX].second < NowW + A[NextX]) {
                    Dist[NextX].second = NowW + A[NextX];
                    PQ.push({ Dist[NextX].first,NextX,NowW + A[NextX] });
                }
            }
        }
    };
}

void settings() {
    Dist[S] = make_pair(0, A[S]);
    dijkstra();
}

void find_Answer() {
    if (Dist[T].first == INF) {
        cout << "-1\n";
    }
    else {
        cout << Dist[T].first << " " << Dist[T].second << "\n";
    }
}

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

    return 0;
}