BOJ31566 힘세고 강한 아침(C++)

---

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

태그 : 그래프 탐색, 플로이드-워셜

---

사고 과정

제한시간이 1초, N <= 100이였다.

20만번의 쿼리 내에 특정 노드를 포함하지 않는 최단 경로를 찾아야 했다.

그 과정에서

1. 20만번 쿼리 내내 다익스트라를 수행해본다. -> 10000 Log20 -> 무조건 시간 초과
2. 전처리로 100번 노드까지 x 99개의 노드 제외하고 x 10000 x Log100 다익스트라 -> 시간 초과
3. 100번노드까지 99개노드 제외한 각 경우에 대해 bfs -> 100^4 -> 1억회. -> 애매하다고 생각.

그래서 뭔가 따로 최적화가 필요하다고 생각해서 고민하고있었는데...

같이 푸시던 분이 n^4 플로이드-워셜로 풀렸다고 하셨다.

그걸 듣고 구현해서 제출했더니 통과되었다.

---

코드

#include <iostream>
using namespace std;

#define INF 1000000007

int n, m, q;

int dist[101][101][101];

void floyd(int ex) {
	for (int node = 1; node <= n; ++node) {
		if (node == ex) {
			continue;
		}
		for (int i = 1; i <= n; ++i) {
			if (i == node || i == ex) {
				continue;
			}
			for (int j = 1; j <= n; ++j) {
				if (j == node || j == ex || i == j) {
					continue;
				}
				if (dist[i][ex][j] > dist[i][ex][node] + dist[node][ex][j]) {
					dist[i][ex][j] = dist[i][ex][node] + dist[node][ex][j];
				}
			}
		}
	}
}

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


	cin >> n >> m >> q;

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			for (int k = 1; k <= n; ++k) {
				dist[i][j][k] = INF;
				
			}
		}
	}

	int a, b, c;
	for (int i = 0; i < m; ++i) {
		cin >> a >> b >> c;

		for (int j = 1; j <= n; ++j) {
			dist[a][j][b] = c;
		}
	}


	for (int ex = 1; ex <= n; ++ex) {
		floyd(ex);
	}


	for (int i = 0; i < q; ++i) {
		cin >> a >> b >> c;

		if (dist[a][b][c] != INF) {
			cout << dist[a][b][c];
		}
		else {
			cout << "No";
		}
		cout << '\n';


	}
}

---

후기

모 대학교 알고리즘 대회에서 출제되었다고 하여 출제 의도까지 읽어보았는데,

n^4이 출제자가 의도한 풀이였다.

개인적으로 그렇다면 시간제한을 1.5초정도로 둬도 되지 않았나 싶다.