[BOJ 22288 // C++] Rainbow Road Race

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 22288번 문제인 Rainbow Road Race이다.
문제는 아래 링크를 확인하자.

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

 

343개의 각 fun location과 지금까지 어떤 색의 에지들을 경유해 지금의 location에 도착했는지(총 128가지 경우의 수)를 묶어 하나의 노드로 생각하면 주어진 문제는 가중치가 있는 그래프에서의 최단거리 문제로 볼 수 있다. 이는 dijkstra 알고리즘을 이용해 해결할 수 있다.

 

각 방문상태를 bitmask를 이용해 표현해 효율적으로 구현하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int N, M;
vector<pair<int, pair<int, int>>> G[344];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
int dist[344][128];
void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	dist[1][0] = 0;
	pq.push(make_pair(0, make_pair(1, 0)));
	while (!pq.empty()) {
		int cur = pq.top().second.first, b = pq.top().second.second, d = pq.top().first; pq.pop();
		if (dist[cur][b] < d) continue;
		for (auto &p:G[cur]) {
			int nxt = p.first, dd = d + p.second.first, bb = b | p.second.second;
			if (dd < dist[nxt][bb]) dist[nxt][bb] = dd, pq.push(make_pair(dd, make_pair(nxt, bb)));
		}
	}
}

int ctoi[128];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ctoi['R'] = 1, ctoi['O'] = 2, ctoi['Y'] = 4, ctoi['G'] = 8, ctoi['B'] = 16, ctoi['I'] = 32, ctoi['V'] = 64;

	cin >> N >> M;
	while (M--) {
		int x, y, d; char c; cin >> x >> y >> d >> c;
		G[x].emplace_back(make_pair(y, make_pair(d, ctoi[c])));
		G[y].emplace_back(make_pair(x, make_pair(d, ctoi[c])));
	}

	dijkstra();
	cout << dist[1][127];
}