[BOJ/Gold 4] 백준 23030 후다다닥을 이겨 츄르를 받자!(C++)

문제 링크

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

23030번: 후다다닥을 이겨 츄르를 받자!

 

문제

쿠기는 평소 지하철 최단 경로를 탐색하여 소요 시간을 알려주는 '후다다닥' 어플을 사용 중이다. 그러나 쿠기는 걸음이 너무 느려서 '후다다닥'이 알려주는 경로를 따라가면 항상 지하철이 떠나간 빈 플랫폼을 맞이해야 했다.

허탈한 마음에 속상해하던 쿠기는 때마침 창업경진대회가 열린다는 소식을 들었다. 쿠기는 환승 시간과 출발지, 도착지를 입력하면 최단 경로로 이동했을 때 걸리는 소요 시간을 알려주는 어플을 만들어 출품하기로 결심했다.

쿠기가 사는 도시의 지하철 노선은 총 N개가 있으며 1~N까지의 번호로 노선을 구분한다. 각 노선에는 최소 1개, 최대 50개의 역이 있다. 노선에 속한 역에는 가장 왼쪽 끝에 위치한 역을 1번으로 하여 1씩 증가하는 번호가 주어진다. 역 번호가 1씩 차이나는 두 역은 인접하다고 말할 수 있다. 하나의 역에서 인접한 역사이의 거리는 일정하여 지하철을 통해 이동하는 데 모두 1만큼의 시간이 걸린다. 지하철은 양방향 모두 통행이 가능하며, 지하철의 방향을 바꿔타는 시간과 지하철을 타기 위해 대기하는 시간은 걸리지 않는다.

쿠기가 사는 도시의 지하철에는 M개의 환승역이 존재한다. 두 개의 노선이 하나의 역에서 만나는 지점을 환승역이라고 한다. 환승역에 3개 이상의 노선이 겹치는 일은 존재하지 않는다. 환승을 하는 경우 걸어서 이동해야 하므로 사용자는 각자 자신이 환승을 하는 데 걸리는 시간 T를 입력한다. 모든 환승역에서 걸어야 하는 거리는 동일하며, 모든 요청에 대해 항상 도착할 수 있다.

하지만 쿠기는 프로그래밍을 할 줄 모르기 때문에 츄르 100개를 걸고 대신 코드를 짜줄 사람을 찾고 있다.

맛있는 츄르를 얻어보자. 사용자가 환승 시간 T와 출발지, 도착지를 입력하면 최단 경로로 이동하였을 때 걸리는 소요 시간을 알려주는 프로그램을 만들어야 한다.

입력

첫째 줄에 노선의 개수 N(2 ≤ N ≤ 10)이 주어진다.

둘째 줄에 N개의 노선별로 속한 역의 개수가 차례로 주어진다. (1 ≤ 역의 수 ≤ 50)

셋째 줄에 환승역의 개수 M(1 ≤ M ≤ ⌊모든 역의 수 / 2⌋)이 주어진다.

넷째 줄부터 M개의 줄에 환승역의 정보가 주어진다.

각 줄은 네개의 양의 정수 P1, P2, Q1, Q2로 구성되며 P1번 노선의 P2역과 Q1번 노선의 Q2역이 연결된 환승역이라는 것이다. 이미 환승역으로 주어진 역은 중복되게 주어지지 않는다.

그 다음 줄에는 사용자의 요청 개수 K(1 ≤ K ≤ 1,000)가 주어진다.

이어서 K개의 줄에 걸쳐 5개의 양의 정수 T(0 ≤ T ≤ 1,000), U1, U2, V1, V2가 주어지며, 환승에 걸리는 소요 시간이 T이며 출발지는 U1번 노선의 U2역이고 도착지는 V1번 노선의 V2역이라는 뜻이다.

출력

각 사용자의 요청에 대하여 출발지에서 도착지로 가는 최단 시간을 한 줄에 하나씩 출력한다.

예제 입력 1

3
14 14 16
6
1 5 2 3
1 6 3 2
1 10 2 9
1 12 3 13
2 5 3 5
2 13 3 15
2
0 2 2 3 14
5 1 3 2 4

예제 출력 1

9
8

알고리즘 분류

• 최단 거리 알고리즘

풀이

주어진 정보를 입력받고, 환승역끼리 연결시켜 준다.

그리고 K번의 다익스트라를 실행하면서 각각 (U1, U2)에서 (V1, V2)까지 가는 데 걸리는 최소 비용을 구한다.

다익스트라를 실행하면서 같은 노선의 전 번호 역, 다음 번호 역, 그리고 환승역이 존재한다면 환승역으로 이동할 수 있다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 51
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int Cost, L, S;
};

struct COMP {
	bool operator()(INFO A, INFO B) {
		return (A.Cost > B.Cost);
	}
};

int N, M, K;
int Station[11];
vector<pair<int, int> > Edge[11][MAX];
int Cost[11][MAX];
int answer;

void Init() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= Station[i]; j++) {
			Cost[i][j] = INF;
		}
	}
	answer = INF;
}

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> Station[i];
		for (int j = 1; j <= Station[i]; j++) {
			Cost[i][j] = INF;
		}
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		int P1, P2, Q1, Q2;
		cin >> P1 >> P2 >> Q1 >> Q2;
		Edge[P1][P2].push_back(make_pair(Q1, Q2));
		Edge[Q1][Q2].push_back(make_pair(P1, P2));
	}
}

void Dijkstra(int T, int U1, int U2, int V1, int V2) {
	priority_queue<INFO, vector<INFO>, COMP> PQ;
	Cost[U1][U2] = 0;
	PQ.push({ 0,U1,U2 });

	while (!PQ.empty()) {
		INFO CurInfo = PQ.top();
		PQ.pop();
		int CurCost = CurInfo.Cost;
		int L = CurInfo.L;
		int S = CurInfo.S;

		if ((L == V1) && (S == V2)) {
			answer = CurCost;
			return;
		}

		if (Cost[L][S] < CurCost) {
			continue;
		}

		int nextL, nextS;
		// 같은 노선 왼쪽
		nextL = L;
		nextS = S - 1;
		if (Cost[nextL][nextS] > CurCost + 1) {
			Cost[nextL][nextS] = CurCost + 1;
			PQ.push({ Cost[nextL][nextS],nextL,nextS });
		}

		// 같은 노선 오른쪽
		nextL = L;
		nextS = S + 1;
		if (Cost[nextL][nextS] > CurCost + 1) {
			Cost[nextL][nextS] = CurCost + 1;
			PQ.push({ Cost[nextL][nextS],nextL,nextS });
		}

		// 환승역이 존재할 때
		for (int i = 0; i < Edge[L][S].size(); i++) {
			nextL = Edge[L][S][i].first;
			nextS = Edge[L][S][i].second;
			if (Cost[nextL][nextS] > CurCost + T) {
				Cost[nextL][nextS] = CurCost + T;
				PQ.push({ Cost[nextL][nextS],nextL,nextS });
			}
		}
	};
}

void Find_Answer() {
	cin >> K;
	for (int i = 0; i < K; i++) {
		Init();
		int T, U1, U2, V1, V2;
		cin >> T >> U1 >> U2 >> V1 >> V2;
		Dijkstra(T, U1, U2, V1, V2);
		cout << answer << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}