11403번: 경로 찾기

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

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("input.txt", "rt", stdin);

	vector<vector<int>> Graph(100, vector<int>(100, 2147000000));

	int N{}, Route{};
	cin >> N;

	for (int i{}; i < N; ++i)
	{
		for (int j{}; j < N; ++j)
		{
			cin >> Route;
			if (Route)
			{
				Graph[i][j] = Route;
			}
			/*if (i == j)
			{
				Graph[i][j] = 1;
			}*/
		}
	}

	for (int k{}; k < N; ++k)
	{
		for (int i{}; i < N; ++i)
		{
			for (int j{}; j < N; ++j)
			{
				if (2147000000 == Graph[i][k] || 2147000000 == Graph[k][j]) continue;
				Graph[i][j] = min(Graph[i][j], Graph[i][k] + Graph[k][j]);
			}
		}
	}

	for (int i{}; i < N; ++i)
	{
		for (int j{}; j < N; ++j)
		{
			if (2147000000 == Graph[i][j])
			{
				cout << "0 ";
			}
			else
			{
				cout << "1 ";
			}
		}

		cout << '\n';
	}

	return 0;
}