[BOJ/Gold 4] 백준 12442 약속장소 정하기 (Large)(C++)

문제 링크

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

12442번: 약속장소 정하기 (Large)

 

문제

서로 다른 도시에 사는 친구들이 급히 약속장소를 정하려고 한다. 하지만 길이 너무 복잡하고 서로 멀리 살아서, 어느 정도 시간 여유를 잡아야 할지 알아내기가 어렵다. 친구들이 한 곳에서 만나는 데 걸리는 최소한의 시간은 얼마인가?

약속장소를 잡기 위해 펼친 지도에는 도시와 각 도시를 잇는 도로에 대한 정보가 있다. 이것은 두 도시를 연결하는 길을 의미하는 것이 아니라, 연속된 길들의 집합으로서 여러 도시를 지나간다.

더욱 자세히 말하면, 각각의 T 개의 테스트 케이스에 대해 다음과 같은 것이 주어진다.

• N: 도시의 숫자
• P: 친구의 수
• M: 도로의 숫자

각 도시는 순서대로 1부터 N까지의 번호가 붙여져 있다.

또한, 1부터 P까지의 번호가 붙여져 있는 각 친구 i에 대해, 다음과 같은 것이 주어진다.

• Xi: 친구가 출발하는 도시의 번호.
• Vi: 친구가 거리 1 만큼 움직이는 데 걸리는 시간.

 

각 도시를 잇는 도로 j에 대해서는 다음과 같은 것이 주어진다. 도로는 단순히 두 도시를 잇는 길이 아니라, 여러 도시를 순서대로 잇는 연속된 길의 모임이다.

• Dj: 도로가 지나가는 도시들 사이의 거리. (한 도로 위에서, 인접한 도시 사이의 거리는 Dj로 같다.)
• Lj: 도로가 지나가는 도시들의 숫자
• {Cj,k}: 도로가 이어주는 도시의 번호가 순서대로 나열된다.

 

위의 정보들을 이용해서, 동시에 출발한 친구들이 한 도시에서 만나는 데 필요한 최소한의 시간을 구하시오. 만약 다들 모일 수 있는 도시가 없다면 '-1'을 대신 출력하시오.

모임은 도시에서만 이루어질 수 있으며, 먼저 도착한 친구들은 다른 친구들을 기다릴 수 있다.

두 도시를 바로 연결하는 도로는 둘 이상 존재할 수 없으며, 어떤 도시에 도착하였을 때, 해당 도시를 지나는 도로 간의 이동은 추가 시간 없이 자유로이 할 수 있다.

입력

입력은 다음과 같은 형식으로 주어진다.

T
N P M
X1 V1
X2 V2
...
XP VP
D1 L1 C1,1 C1,2 ... C1,L1
D2 L2 C2,1 C2,2 ... C2,L2
...
DM LM CM,1 CM,2 ... CM,LM
N' P' M'
....

제한

• 각 테스트 케이스에 대한 답은 2147483647 이하이다.
• 1 ≤ T ≤ 30.
• 1 ≤ Vi ≤ 200.
• 1 ≤ Di ≤ 200.
• 2 ≤ Lj ≤ N.
• 1 ≤ N ≤ 10000.
• 2 ≤ P ≤ 100.
• 1 ≤ M ≤ 1000.
• 2 ≤ Lj≤ 150.

출력

각각의 테스트 케이스에 대해서, x가 1번부터 시작하는 케이스 번호라고 하고 y가 각 케이스에 해당하는 답이라고 할 때 출력 파일의 각 줄에 "Case #x: y"와 같은 형식으로 출력한다. 친구들이 한 도시에서 만나는 것이 불가능하다면, 최소 시간 대신 '-1'을 출력한다.

예제 입력 1

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

예제 출력 1

Case #1: 1
Case #2: 3
Case #3: -1

힌트

알고리즘 분류

• 최단 거리 알고리즘

풀이

먼저 P명의 친구들의 출발 도시 및 거리 1만큼 가는 데 걸리는 시간 정보를 구조체와 벡터를 사용해서 관리한다.

M개의 도로 정보는 L개의 도시들을 순서대로 거리 D만큼 이어주도록 간선 정보를 관리한다.

그리고 다익스트라를 수행하는데, 최대 P번의 다익스트라를 수행하게 된다.

1번 친구가 모든 도시에 도착했을 때의 각각의 최단 거리, 2번 친구가 모든 도시에 도착했을 때의 각각의 최단 거리, ..., P번 친구가 모든 도시에 도착했을 때의 각각의 최단 거리를 구하는 것이다.

마지막으로 N개의 도시 각각의 모든 친구들이 모일 수 있는 최단 시간을 구한다.

친구들이 i번 도시까지 도착하는 데 걸리는 최단 시간을 따져서 가장 오래 걸리는 시간이 i번 도시로 모두 모였을 때 걸리는 최단 시간이다.

만약에 특정 친구가 특정 도시에 도착하지 못 하는 경우에는 해당 도시를 제외한다.

특정 도시로 모였을 때 걸리는 시간 중 가장 최소인 시간이 정답이 되며, 어떠한 도시에도 모든 친구들이 모일 수 없다면 -1을 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX_N 10001
#define MAX_F 101
#define INF 2e9
#define FASTIO cin.tie(0); cout.tie(0);

using namespace std;
struct FRIENDS {
    int X, V;
};

int T, N, P, M;
int Dist[MAX_F][MAX_N];
vector<FRIENDS> Friends;
vector<pair<int, int> > Edge[MAX_N];
int Answer;

void init() {
    Friends.clear();
    for (int i = 0; i < MAX_N; i++) {
        Edge[i].clear();
    }
    for (int i = 0; i < MAX_F; i++) {
        for (int j = 0; j < MAX_N; j++) {
            Dist[i][j] = INF;
        }
    }
    Answer = INF;
}

void dijkstra(int index) {
    int Start = Friends[index].X;
    int Cost = Friends[index].V;
    priority_queue<pair<int, int> > PQ;
    Dist[index][Start] = 0;
    PQ.push(make_pair(0, Start));
    
    while (!PQ.empty()) {
        int CurD = -PQ.top().first;
        int CurX = PQ.top().second;
        PQ.pop();

        if (Dist[index][CurX] < CurD) {
            continue;
        }

        for (int i = 0; i < Edge[CurX].size(); i++) {
            int NextD = Edge[CurX][i].second;
            int NextX = Edge[CurX][i].first;
            if (Dist[index][NextX] > CurD + NextD) {
                Dist[index][NextX] = CurD + NextD;
                PQ.push(make_pair(-Dist[index][NextX], NextX));
            }
        }
    };
    for (int i = 1; i <= N; i++) {
        if (Dist[index][i] != INF) {
            Dist[index][i] *= Cost;
        }
    }
}

void settings() {
    for (int i = 0; i < Friends.size(); i++) {
        dijkstra(i);
    }
    for (int i = 1; i <= N; i++) {
        int Cur = 0;
        for (int j = 0; j < Friends.size(); j++) {
            if (Dist[j][i] == INF) {
                Cur = -1;
                break;
            }
            Cur = max(Cur, Dist[j][i]);
        }
        if (Cur == -1) {
            continue;
        }
        Answer = min(Answer, Cur);
    }
}

void find_Answer(int index) {
    if (Answer == INF) {
        cout << "Case #" << index << ": -1\n";
    }
    else {
        cout << "Case #" << index << ": " << Answer << "\n";
    }
}

void input() {
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> N >> P >> M;
        init();
        for (int j = 1; j <= P; j++) {
            int X, V;
            cin >> X >> V;
            Friends.push_back({ X,V });
        }
        for (int j = 1; j <= M; j++) {
            int D, L;
            cin >> D >> L;
            vector<int> Vec;
            for (int k = 0; k < L; k++) {
                int C;
                cin >> C;
                Vec.push_back(C);
            }
            for (int k = 1; k < Vec.size(); k++) {
                int Prev = Vec[k - 1];
                int Next = Vec[k];
                Edge[Prev].push_back(make_pair(Next, D));
                Edge[Next].push_back(make_pair(Prev, D));
            }
        }
        settings();
        find_Answer(i);
    }
}

int main() {
    FASTIO
    input();

    return 0;
}