11404 플로이드

플로이드 워샬 문제

주의할점.

• 1) 내자신의 dist는 0이다. 라는 것을 머리에 넣자!

• 2) 최소거리를 찾아나서는 것이므로, 반드시 초기값을 크게
  하지만, 카카오의 경우 합승택시에서 틀린 적이 있으므로.

  : 모든 노드의 수 * 최대 비용 + 1
  // 이렇게 설정하는 것이 안전함.

• 3) 마지막에 경로가 연결되어 있지 않아서 출력을 해야하느데,
  초기값이 ,maxx 값으로 되어 있는 경우를 생각하자.
  갱신이 안된 부분들이 있을 수 있음. 간선이 없는 경우!
  -> 이때는 출력할때 maxx값일 경우에, 0으로 출력하자.

• 그림 1번 : 초기값 셋팅 및, 나자신의 거리는 0으로 설정하기
  

• 그림 2번 : 플로이드 워셜 dp식과 출력 처리하기
  

코드

#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>
#include <queue>
#include <stack>
#include <map>


// 22:00~~ 
//int v[101][101];
const int maxx = 100 * 100000 + 1;

vector<vector<int>>v(101, vector<int>(101, maxx));
int main() 
{
	int n, m;
	cin >> n >> m;

	// n은 도시의 개수 
	// m은 버스의 개수 


	//fill(begin(v), end(v), maxx);

	// 자기자신의 값은 비용이 전혀 없음.
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (i == j)
			{
				v[i][j] = 0;
			}
		}
	}

	for (int i = 0; i < m; ++i)
	{
		int a, b, c;
		cin >> a >> b >> c;
		
		
		v[a][b] = min(v[a][b], c);
	}

	// 플로이드 워셜 
	// dist(a , b) : a에서 비로 가는 최소한의 거리
	// min(dist[a][b] , dist[a][k] , dist[k][b]);

	for (int k = 1; k <= n; ++k)
	{
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= n; ++j)
			{
				v[i][j] = min(v[i][j], v[i][k] + v[k][j]);
			}
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (v[i][j] == maxx)
			{
				cout << 0 << " ";
			}
			else
			{
				cout << v[i][j] << " ";

			}
		}
		cout << '\n';
	}

}