[알고리즘] 백준 1613번: 역사 (C++)

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

1613번: 역사

또 똑같은 키워드다.

(https://draw-code-boy.tistory.com/151)

(https://draw-code-boy.tistory.com/153)

다만, 시간 초과가 나와서

ios_base::sync_with_stdio(false);
cin.tie(NULL);

를 해주고,

값을 복사해주는 cache의 역할이 사실상 의미가 없기 때문에

graph에 입력받은 값을 복사하지 않고, 즉각적으로 cache에 입력을 받고, 플로이드 와샬을 돌렸다.

 

[키워드]

플로이드 와샬로 각 노드 간의 전후 관계(?), 관련 있는 노드가 몇 개인가 등 여러 문제를 풀 수 있는 것을 알아냈다.

 

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX 500 + 1
#define INF 987654321
using namespace std;

int cache[MAX][MAX];
int n, m;

void floydWarshall() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (cache[i][k] != INF && cache[k][j] != INF) {
					cache[i][j] = min(cache[i][j], cache[i][k] + cache[k][j]);
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) cache[i][j] = 0;
		}
	}
}

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

	cin >> n >> m;

	// init
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cache[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		cache[a][b] = 1;
	}

	floydWarshall();

	int s;
	cin >> s;
	for (int i = 0; i < s; i++) {
		int a, b;
		cin >> a >> b;
		if (cache[a][b] != 0 && cache[a][b] != INF) {
			cout << -1 << '\n';
		}
		else if (cache[b][a] != 0 && cache[b][a] != INF) {
			cout << 1 << '\n';
		}
		else {
			cout << 0 << '\n';
		}
	}

	return 0;
}