득이공간
[백준 C++] 11403 경로 찾기 - 플로이드워셜 본문
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
cpp
#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값을 넣어주면 됩니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
| [백준 C++] 1922 네트워크 연결 - 최소신장트리 (0) | 2024.02.03 |
|---|---|
| [백준 C++] 1197 최소 스패닝 트리 - 최소신장트리 (0) | 2024.02.03 |
| [백준 C++] 11404 플로이드 - 플로이드워셜 (0) | 2024.02.02 |
| [백준 C++] 1865 웜홀 - 벨만포드 (0) | 2024.02.02 |
| [백준 C++] 11657 타임머신 - 벨만포드 (0) | 2024.02.02 |
'PS/알고리즘 문제풀이' Related Articles
more
