[백준 C++] 11404 플로이드 - 플로이드워셜

11404번: 플로이드

cpp

#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. 점화식 업데이트 시 경유지로 갈 수 없는 경우를 패스한다.