[백준] 11562번 - 백양로 브레이크 (C++) 문제 및 풀이

문제) 백준 - 플루이드 와샬 - 백양로 브레이크

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

11562번: 백양로 브레이크

 

건물의 수(n)가 250 이하이기 때문에 O(n^3)의 시간 복잡도를 가진 플루이드 와샬로 풀이가 가능합니다. 양방향 길은 모두 0, 일방통행 길은 한 방향은 0으로 나머지는 1로 부여해 플루이드 와샬을 진행합니다.

 

C++ 소스코드)

	for (int i = 0; i < M; ++i) {
	int u, v, b; cin >> u >> v >> b;
	if (b == 1) {
	board[u][v] = 0;
	board[v][u] = 0;
	}
	else {
	board[u][v] = 0;
	board[v][u] = 1;
	}
	}
	for (int t = 1; t <= N; ++t)
	for (int i = 1; i <= N; ++i)
	for (int j = 1; j <= N; ++j)
	board[i][j] = min(board[i][j], board[i][t] + board[t][j]);

view raw 11562.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/11562_%EB%B0%B1%EC%96%91%EB%A1%9C%20%EB%B8%8C%EB%A0%88%EC%9D%B4%ED%81%AC.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions