득이공간
[백준 C++] 11404 플로이드 - 플로이드워셜 본문
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int& Infinite = INT_MAX;
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] == Infinite
|| Distance[K][End] == Infinite)
{
continue;
}
Distance[Start][End] = min(Distance[Start][End], Distance[Start][K] + Distance[K][End]);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin >> N >> M;
Distance.reserve(N);
for (int i = 0; i < N; ++i)
{
Distance.emplace_back(vector<int>(N, Infinite));
Distance[i][i] = 0;
}
for (int i = 0; i < M; ++i)
{
int Start, End, Weight;
cin >> Start >> End >> Weight;
Distance[Start - 1][End - 1] = min(Distance[Start - 1][End - 1], Weight);
}
FloydWarshall(N);
for (const vector<int>& Row : Distance)
{
for (const int& Weight : Row)
{
if (Weight == Infinite)
{
cout << 0;
}
else
{
cout << Weight;
}
cout << ' ';
}
cout << '\n';
}
}
플로이드-워셜 알고리즘 문제입니다.
중요 포인트는 다음과 같습니다.
1. 버스 정보를 입력 받을 때 이미 값이 존재하면 둘 중에 작은 값을 저장한다.
2. 점화식 업데이트 시 경유지로 갈 수 없는 경우를 패스한다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 1197 최소 스패닝 트리 - 최소신장트리 (0) | 2024.02.03 |
---|---|
[백준 C++] 11403 경로 찾기 - 플로이드워셜 (0) | 2024.02.02 |
[백준 C++] 1865 웜홀 - 벨만포드 (0) | 2024.02.02 |
[백준 C++] 11657 타임머신 - 벨만포드 (0) | 2024.02.02 |
[백준 C++] 1238 파티 - 다익스트라 (2) | 2024.02.02 |