백준 11404 플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 10000001

vector < vector <int> > arr(101, vector <int>(101, INF));


int main()
{
	int n, m;
	cin >> n >> m;

	


	int a, b, c;
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b >> c;
		if(arr[a][b]>c)
		arr[a][b] = c;
	}
	// 비용 입력


	//플로이드와샬인지 뭔지

	for (int i = 1; i <= n; i++) //중간점
	{
		for (int j = 1; j <= n; j++) //출발
		{
			for (int k = 1; k <= n; k++) //도착
			{
				if (i == j || j == k || i == k)continue; //자기 스스로의 길은 의미가 없어 시간복잡도를 조금이나마 최소화

				if (arr[j][i] != INF && arr[i][k] != INF)
				{
					arr[j][k] = min(arr[j][k],arr[j][i] + arr[i][k]);
				
		
				}
			}
		}
	}

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

	

}

지난주에 풀었던 키순서 문제와 비슷한 유형으로 플로이드 와샬을 다시 한번 풀어볼겸 찾아봤다

bbakssang.tistory.com/17

백준 2458 키순서

 

다만 저번에 풀었던 문제에서는 1로 경로가 있음을 확인하였지만 이번에는 가는 비용 c를 입력받음으로써

초기값이였던 INF가 아닐경우 c로 길이있음과 비용을 동시에 풀었다