[백준] 11404 플로이드

[백준11404]플로이드

제목부터 플로이드.

#include <iostream>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;

int N; //도시 수
int M; //버스 수
int price[101][101];

void floyd() {

	//via번째 도시를 거쳐가는게 더 빠를 경우 update

	for (int via = 1; via <= N; via++) {
		for (int from = 1; from <= N; from++) {
			if (price[from][via] == 0)
				continue;
			for (int to = 1; to <= N; to++) {
				if (price[via][to] == 0 || from == to) {
					continue;
				}
				if (price[from][to] == 0 || price[from][to] > price[from][via] + price[via][to]) {
					price[from][to] = price[from][via] + price[via][to];
				}
			}
		}
	}
}


int main() {

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int start, end, price_;
		scanf("%d %d %d", &start, &end, &price_);
		
		if (price[start][end] == 0) {
			price[start][end] = price_;
		}
		else {
			price[start][end] = min(price[start][end], price_);

		}
	}

	floyd();

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << price[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;

}