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

#include <iostream>
#include <vector>
#include <queue>
 
int n = 0;
int m = 0;
int visit[101] = {};
std::vector<std::pair<int, int>> vec[101] = {};
 
void Dijkstra(int iStart)
{
	std::priority_queue < std::pair<int, int>, 
		std::vector<std::pair<int, int>>, 
		std::greater<std::pair<int, int>>> pri_que = {};
	pri_que.push({0, iStart});
	visit[iStart] = 0;
 
	while (!pri_que.empty())
	{
		int iCost = pri_que.top().first;
		int iNow = pri_que.top().second;
		pri_que.pop();
 
		for (int i = 0; i < vec[iNow].size(); ++i)
		{
			int iNextCost = vec[iNow][i].second;
			int iNext = vec[iNow][i].first;
 
			if (visit[iNext] > iNextCost + iCost)
			{
				visit[iNext] = iNextCost + iCost;
				pri_que.push({iNextCost + iCost, iNext});
			}
		}
	}
}
 
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cin >> n >> m;
 
	for (int i = 0; i < m; ++i)
	{
		int a = 0;
		int b = 0;
		int c = 0;
 
		std::cin >> a >> b >> c;
 
		vec[a].push_back({b, c});
	}
 
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			visit[j] = 2147483647;
		}
 
		Dijkstra(i);
 
		for (int j = 1; j <= n; ++j)
		{
			if (visit[j] == 2147483647)
			{
				std::cout << "0 ";
			}
 
			else
			{
				std::cout << visit[j] << " ";
			}
		}
 
		std::cout << "\n";
	}
 
	return 0;
}

저는 보자마자 다익스트라자다!

하고 한점에서 가는 비용을 찾았습니다.

근데... 플로이드 와샬 알고리즘을 사용해서 하는 게 더 빠르더라구요...

한 점에서 찾는 건 다익스트라자

여러 점에서 여러 점은 플로이드 와샬! 알고리즘을 생각하시면 될 것 같습니다.

물론 플로이드 와샬은 3중포문이라 느릴 줄 알았는데 100개가 최대라서 플로이드 와샬이 좀 더 빨랐습니다.

여기서 플로이드 와샬은 i -> j -> k 일 때 i -> k 의 값을 정해주는 것입니다.