[BOJ/Gold 4] 백준 32197 절연 구간 최소화(C++)

문제 링크

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

 

문제

지하철의 전기를 공급받는 방식(급전 방식)은 직류와 교류로 구분된다. 열차 운행 중 급전 방식이 바뀌게 되면 잠시 전력 공급이 중단된다. 이러한 현상을 절연이라 부른다. 열차 탑승객의 만족도는 절연이 적게 발생할수록 높아진다.

서울특별시에는 N개의 지하철역이 있고, 두 역을 직접 잇는 선로 M개가 설치되어 있다. 각 역에는 1부터 N번까지의 번호가, 선로에는 1부터 M번까지의 번호가 붙어있다. 설치되어 있는 선로만으로 임의의 두 역 사이를 이동할 수 있다. 각 선로는 직류 또는 교류 중 하나의 방식으로 전기를 공급하며 양방향으로 통행할 수 있다.

열차는 어떤 역과 이어진 선로를 통해 다른 역으로 이동하는 과정을 몇 번이든 반복할 수 있다. 이 때, 이용하는 선로의 급전 방식이 직류에서 교류로, 또는 교류에서 직류로 바뀐다면 절연이 발생한다.

당신은 열차 기관사이다. 당신은 A번 역에서 출발해서, 선로를 통해 B번 역까지 열차를 운행하고자 한다. 이 때 절연이 일어나는 횟수를 최소로 하는 경로로 운행할 때, 절연이 몇 번 발생하는지 구해보자.

 

입력

첫 줄에 지하철역의 수 N과 선로의 수 M이 정수의 형태로 사이에 공백을 두고 주어진다.

다음 M개의 줄에 걸쳐, i (1 ≤ i ≤ M)번째 줄에 세 정수 Si, Ei, Ti가 사이에 공백을 두고 주어진다. 이는 i번 선로가 Si번 역과 Ei번 역을 직접 연결하며, Ti = 0이라면 직류로, Ti = 1이라면 교류로 전기를 공급받음을 나타낸다.

다음 줄에 시작 역과 끝 역을 나타내는 두 정수 A, B가 사이에 공백을 두고 주어진다.

 

출력

 A번 역에서 B번 역까지 열차를 운행할 때 급전 방식이 바뀌는 최소 횟수를 정수의 형태로 출력한다.

 

제한

• 주어지는 모든 수는 정수이다.
•  2 ≤ N ≤ 100,000
•  1 ≤ M ≤ 150,000
•  1 ≤ Si ≤ N
•  1 ≤ Ei ≤ N
•  Si ≠ Ei
•  Ti = 0 혹은 Ti = 1
•  1 ≤ A ≤ N
•  1 ≤ B ≤ N
•  A ≠ B
• 임의의 두 역 사이를 주어진 선로를 이용해 이동할 수 있다.
• 두 역을 직접 잇는 선로는 최대 한 개 존재한다.

 

예제 입력 1

3 2
1 2 0
2 3 1
1 3

예제 출력 1

1

예제 입력 2

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

예제 출력 2

0

 

알고리즘 분류

• 최단 거리 알고리즘

 

풀이

절연이 발생할 때는, 최근 T값과 다음 간선의 T값이 다를 때이므로 XOR 연산자를 이용해서 절연 발생 횟수를 더해준다.

 

코드

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

using namespace std;
int N, M, S, E, T, A, B;
int Dist[MAX];
vector<pair<int, int> > Edges[MAX];

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

void input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> S >> E >> T;
		Edges[S].push_back(make_pair(E, T));
		Edges[E].push_back(make_pair(S, T));
	}
	cin >> A >> B;
}

void dijkstra() {
	priority_queue<pair<int, pair<int, int> > > PQ;
	PQ.push(make_pair(0, make_pair(A, -1)));
	Dist[A] = 0;

	while (!PQ.empty()) {
		int NowT = -PQ.top().first;
		int NowX = PQ.top().second.first;
		int NowM = PQ.top().second.second;
		PQ.pop();

		for (int i = 0; i < (int)Edges[NowX].size(); i++) {
			int NextX = Edges[NowX][i].first;
			int NextM = Edges[NowX][i].second;
			if (NowM == -1) {
				if (Dist[NextX] > Dist[NowX]) {
					Dist[NextX] = Dist[NowX];
					PQ.push(make_pair(-Dist[NextX], make_pair(NextX, NextM)));
				}
			}
			else {
				if (Dist[NextX] > Dist[NowX] + (NextM ^ NowM)) {
					Dist[NextX] = Dist[NowX] + (NextM ^ NowM);
					PQ.push(make_pair(-Dist[NextX], make_pair(NextX, NextM)));
				}
			}
		}
	};
}

void settings() {
	dijkstra();
}

void printAnswer() {
	cout << Dist[B] << "\n";
}

int main() {
    FASTIO

	init();
	input();
	settings();
    printAnswer();

    return 0;
}