[C++] 백준 11404번: 플로이드

🔗 문제

11404번: 플로이드

11404번: 플로이드

 

✍️ 풀이

 

제목부터 거저주는 플로이드 기초 문제 

 

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

플로이드 와샬이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

그렇다면 A→B 중 가장 작은 비용 값을 저장하자.

 

💾  소스

#include <iostream>
#include <vector>
#include <cmath>

const int INF = 1e9;

std::vector<std::vector<int>> adj;
int N, M;

void input()
{
	int a, b, c;

	std::cin >> N >> M;

	adj.resize(N + 1, std::vector<int>(N + 1, INF));
	
	for (int i = 1; i <=N; ++i)
		adj[i][i] = 0;

	for(int i=0; i<M; ++i)
	{
		std::cin >> a >> b >> c;

		if(adj[a][b] > c) // 같은 노선이면 가장 작은 비용만 저장
			adj[a][b] = c;
	}
}

int main()
{

	input();
	
	for (int i = 1; i <= N; ++i) // 중간 노드
	{
		for (int j = 1; j <= N; ++j)
		{
			for (int k = 1; k <= N; ++k)
			{
				if (i == j || k == i || k == j) continue;

				adj[j][k] = std::min(adj[j][k], adj[j][i] + adj[i][k]);
			}
		}
	}

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			std::cout << (adj[i][j] == INF ? 0 : adj[i][j]) << ' ';
		}
		std::cout << '\\n';
	}

	return 0;
}