[BOJ] 25636 - 소방차

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

BOJ - 소방차

문제 유형: 그래프, 다익스트라

문제 난이도: Gold III

시간 제한: 2초

메모리 제한: 512MB

 

문제

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

소방차에는 물을 담을 수 있는 물탱크가 있어서 이곳에 담은 물을 화재를 진압하는데에 사용할 수 있다. 소방차는 소방서에서 물탱크가 빈 상태로 출동하지만, 이동 중에 교차로에 도착할 때마다 교차로에 설치된 소화전을 이용해서 물탱크에 물을 충전한다. 소방차가 i$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만을 출력한다.

 

풀이

물탱크 배열 wtank를 만든다.

경로를 받아서 인접리스트를 구성해준다.

 

그러고, s로부터의 최단거리를 담는 dist와 충전하는 물의양을 계산하는 gain배열을 만든다.

다익스트라를 돌리는데, 새로운 노드로 가는 조건은 dist가 더 낮아서 업데이트되거나, 같은 dist인경우에 더 많은 gain인 경우 업데이트 되도록 했다.

 

그러고 우선순위 큐는 <비용, 물의양, 노드>로 구성하여 최소힙으로 구성했다.

가중치나 물의 양의 값의 범위가 크기에, 8바이트 정수를 이용해야 한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using tlll = tuple<ll, ll, ll>;

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<ll> wtank(n);
    vector<vector<pll>> adj(n);
    for (auto &w : wtank) cin >> w;

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    int s, t;
    cin >> s >> t;
    s--;
    t--;

    vector<ll> dist(n, LLONG_MAX);
    vector<ll> gain(n, 0);
    dist[s] = 0;
    gain[s] = wtank[s];

    priority_queue<tlll, vector<tlll>, greater<>> pq;  // dist, gain, node;
    pq.emplace(dist[s], gain[s], s);

    while (!pq.empty()) {
        auto [currDist, currGain, currNode] = pq.top();
        pq.pop();

        if (currDist > dist[currNode] ||
            (currDist == dist[currNode] && currGain < gain[currNode]))
            continue;

        for (const auto &[nextNode, nextWeight] : adj[currNode]) {
            if (dist[nextNode] > currDist + nextWeight ||
                (dist[nextNode] == currDist + nextWeight &&
                 gain[nextNode] < currGain + wtank[nextNode])) {
                dist[nextNode] = currDist + nextWeight;
                gain[nextNode] = currGain + wtank[nextNode];
                pq.emplace(dist[nextNode], gain[nextNode], nextNode);
            }
        }
    }

    if (dist[t] == LLONG_MAX)
        cout << "-1\n";
    else
        cout << dist[t] << " " << gain[t] << "\n";

    return 0;
}