[백준 C++] 11403 경로 찾기 - 플로이드워셜

11403번: 경로 찾기

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

vector<vector<int>> Distance;

void FloydWarshall(int N)
{
	for (int K = 0; K < N; ++K)
	{
		for (int Start = 0; Start < N; ++Start)
		{
			for (int End = 0; End < N; ++End)
			{
				if (Distance[Start][K] == 0
					|| Distance[K][End] == 0)
				{
					continue;
				}

				Distance[Start][End] = 1;
			}
		}
	}
}

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

	int N;
	cin >> N;

	Distance.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		Distance.emplace_back(vector<int>());

		for (int j = 0; j < N; ++j)
		{
			int Edge;
			cin >> Edge;

			Distance.back().emplace_back(Edge);
		}
	}

	FloydWarshall(N);

	for (const vector<int>& Row : Distance)
	{
		for (const int& Edge : Row)
		{
			cout << Edge << ' ';
		}
		cout << '\n';
	}
}

---

일반적인 플로이드-워셜 문제입니다.

점화식 사용 대신 도달 가능한 경우만 판단해서 1값을 넣어주면 됩니다.