[BOJ/Gold 2] 백준 17940 지하철(C++)

문제 링크

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

17940번: 지하철

 

문제

대학원생인 형욱이는 연구실에 출근할 때 주로 지하철을 이용한다. 지하철은 A와 B, 두 개의 회사에서 운영하고 있다. 두 회사는 경쟁사 관계로 사람들이 상대 회사의 지하철을 이용하는 것을 매우 싫어한다. 그래서 A와 B는 모두 상대 회사의 지하철로 환승할 때 마다 비싼 요금을 받고 있다. 

형욱이는 가난한 대학원생이기 때문에 돈을 아끼는 것이 가장 중요하다. 형욱이에게 최적의 출근경로를 찾아주자. 최적의 출근 경로란 환승 횟수를 최소로 하는 경로 중 소요시간이 가장 짧은 경로이다. 여기에서의 환승은 이동하면서 지하철역을 운영하는 회사가 바뀔 때 마다 환승 1회로 계산한다.

위의 그림에서 원은 지하철역을 의미하고 선들은 지하철역들이 연결되어 있는 지를 나타낸다. 흰색으로 표시된 지하철역은 A회사가 운영하는 지하철역이고 검은색으로 표시된 역은 B회사가 운영하는 지하철역이다. 이 때 붉게 표시된 경로로 이동하는 것이 환승 2회로 가장 적게 환승하면서 시간이 가장 짧은 경로이다.

입력

첫째 줄에 지하철역의 수 N과 도착지의 번호 M이 공백을 사이에 두고 정수로 주어진다. 지하철역은 순서대로 0 부터 N-1까지 존재하며 출발지는 항상 0 이다. (2 ≤ N ≤ 1000, 0 < M < 1000)

그 다음 N 줄에 걸쳐 각각의 지하철역을 운영하는 회사의 정보 Ci(0 ≤  i < N)가 0 또는 1로 주어진다. 0은 A회사를 뜻하고 1은 B회사를 뜻한다.

그 다음 N 줄은 지하철역간의 연결 상태 Eij(0 ≤ Eij ≤ 1000)가 정수로 주어진다.  Eij가 0인 경우 i번째 역과 j번째 역이 연결되어 있지 않음을 의미하고 0보다 클 경우 두 역이 연결되어 있으며 이동시간이 Eij라는 것을 의미한다.

출력

최적의 경로를 이용할 때 환승 횟수와 총 소요 시간을 공백으로 구분하여 출력한다.

또한 출발지와 도착지는 무조건 연결되어 있음이 보장된다.

예제 입력 1

6 3
0
1
1
0
1
0
0 3 1 0 10 0
3 0 0 15 0 0
1 0 0 0 0 1
0 15 0 0 10 0
10 0 0 10 0 1
0 0 1 0 1 0

예제 출력 1

2 18

알고리즘 분류

• 최단 거리 알고리즘

풀이

출발지의 위치 0을 시작점으로 하여 다익스트라를 1번 수행한다.

환승 시에는 비용에 엄청나게 큰 값(1e9)를 더해준다. 왜냐하면, 문제에 따르면 환승 횟수가 최대한 적은 경로로 이동한다고 하였으므로, 환승 횟수가 무조건 적은 경로가 우선이다. 따라서 환승할 때 큰 값을 더해 준다면 최대한 환승이 적은 경로로 이동할 것이다.

환승을 한 번 할 때마다 1e9를 더하기 때문에, M까지의 최단 비용에서 1e9를 나눈 몫이 환승 횟수가 될 것이고, 나머지가 최단 비용이 될 것이다.

코드

#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 1001
#define LL long long
#define INF 1e18
#define TRANS 1e9

using namespace std;
int N, M;
LL E[MAX][MAX];
int C[MAX];
LL Cost[MAX];

void Input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		Cost[i] = INF;
	}
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> E[i][j];
		}
	}
}

void Dijkstra() {
	priority_queue<pair<LL, LL> > PQ;
	Cost[0] = 0;
	PQ.push(make_pair(0, 0));

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

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

		for (int i = 0; i < N; i++) {
			if (E[CurX][i] == 0) {
				continue;
			}
			int nextCost = E[CurX][i];
			int nextX = i;
			if (C[CurX] != C[nextX]) {
				if (Cost[nextX] > CurCost + nextCost + TRANS) {
					Cost[nextX] = CurCost + nextCost + TRANS;
					PQ.push(make_pair(-Cost[nextX], nextX));
				}
			}
			else {
				if (Cost[nextX] > CurCost + nextCost) {
					Cost[nextX] = CurCost + nextCost;
					PQ.push(make_pair(-Cost[nextX], nextX));
				}
			}
		}
	};
}

void Find_Answer() {
	cout << Cost[M] / (LL)TRANS << " " << Cost[M] % (LL)TRANS << "\n";
}

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

	return 0;
}