11404번: 플로이드
사용 언어: C++
풀이
모든 지점에서 다른 모든 지점으로의 최솟값을 알아야하므로 플로이드 워셜 알고리즘으로 풀어야함.
2차원 배열을 자기 자신은 0, 그 외에는 0x3f (매우 큰 수)로 초기화하고, s도시에서 e도시로 방향이 있고 가중치 w인 AddEdge(s, e, w)로 2차원 배열에 값들 저장.
Run()은 그냥 모든 점들의 최솟값을 확인하는 함수. G[i][j]와 G[i][k] + G[k][j] 중 최솟값을 계속 업데이트.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int G[101][101];
void Init()
{
memset(G, 0x3f, sizeof G);
// 자기 자신 도시는 0
for (int i = 1; i <= n; i++)
{
G[i][i] = 0;
}
}
// 도시 s -> e, 가중치 w
void AddEdge(int s, int e, int w)
{
G[s][e] = min(G[s][e], w); // 같은 경로 버스들 중 최솟값 받기
}
// 모든 시작점으로부터 모든 도착점으로의 최솟값 업데이트 O(V^3)
void Run()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
Init();
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
AddEdge(a, b, c);
}
Run();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (G[i][j] == 0x3f3f3f3f)
cout << "0 ";
else
cout << G[i][j] << " ";
}
cout << "\n";
}
return 0;
}
'BOJ' 카테고리의 다른 글
9372번: 상근이의 여행 (0) | 2024.10.04 |
---|---|
11657번: 타임머신 (0) | 2024.10.03 |
2252번: 줄 세우기 (0) | 2024.10.01 |
24445번: 알고리즘 수업 - 너비 우선 탐색 2 (0) | 2024.09.30 |
24444번: 알고리즘 수업 - 너비 우선 탐색 1 (0) | 2024.09.30 |