취미로 코딩하기

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

이번에 볼 문제는 백준 1746번 문제인 단체 릴레이이다.
문제는 아래 링크를 확인하자.

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

각 지점에서 다른 지점까지 1번, 2번, ..., 2^K번 움직여 이동하는 최단거리들은 각각 O(V^3) (V는 그래프의 노드 개수)에 구할 수 있다. (Floyd-Warshall과 비슷하게 구현하면 된다.)

이제 N의 이진수 표현과 위에서 구한 최단거리들을 이용하여 각 지점에서 다른 지점까지 N개의 에지를 거쳐 이동하는 최단거리를 구할 수 있다. 이것 또한 Floyd-Warshall의 dp 점화식과 같이 처리하면 계산해낼 수 있다.

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

#include <iostream>
#include <utility>
#include <cstring>
using namespace std;

int idx = 1;
int nodetoidx[1001];
int dist[20][201][201];

int ans[201][201];
int nxt[201][201];

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

	int K, M, S, E; cin >> K >> M >> S >> E;
	while (M--) {
		int x, y, d; cin >> d >> x >> y;
		if (nodetoidx[x] == 0) nodetoidx[x] = idx++;
		if (nodetoidx[y] == 0) nodetoidx[y] = idx++;
		x = nodetoidx[x], y = nodetoidx[y];
		dist[0][x][y] = dist[0][y][x] = d;
	}
	
	for (int r = 1; r < idx; r++) {
		for (int c = 1; c < idx; c++) {
			if (dist[0][r][c] == 0) dist[0][r][c] = 1000000007;
		}
	}

	for (int p = 1; p < 20; p++) {
		for (int r = 1; r < idx; r++) {
			for (int c = r; c < idx; c++) {
				int& d = dist[p][r][c] = 1000000007;
				for (int k = 1; k < idx; k++) {
					d = min(d, dist[p - 1][r][k] + dist[p - 1][k][c]);
				}
				dist[p][c][r] = d;
			}
		}
	}

	for (int r = 1; r < idx; r++) {
		for (int c = 1; c < idx; c++) ans[r][c] = 1000000007;
		ans[r][r] = 0;
	}

	int p = 0;
	while (K) {
		if (K & 1) {
			for (int r = 1; r < idx; r++) {
				for (int c = r; c < idx; c++) {
					int& d = nxt[r][c] = 1000000007;
					for (int k = 1; k < idx; k++) {
						d = min(d, ans[r][k] + dist[p][k][c]);
					}
					nxt[c][r] = d;
				}
			}
			swap(ans, nxt);
		}
		p++;
		K >>= 1;
	}

	S = nodetoidx[S], E = nodetoidx[E];
	cout << ans[S][E];
}