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

https://www.acmicpc.net/problem/11404

11404번: 플로이드

백준 11404번 플로이드를 풀었다.

 

플로이드 와샬 알고리즘을 사용해서 푸는 문제다.

입력받을 때 시작 노드와 도착 노드가 같지만 비용이 다른 버스를 유의해야 한다.

출력할 때 dist배열에 INF로 정한 값이 있다면 갈 수 있는 경로가 없는 것이므로 0으로 바꿔줘야 한다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

#define INF 100000000

int adj[101][101];
int dist[101][101];


int main() {
	int n, m;

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		if (adj[start][end] == 0)
			adj[start][end] = cost;
		else {
			if (adj[start][end] > cost)
				adj[start][end] = cost;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dist[i][j] = 0;
			else if (adj[i][j] != 0)
				dist[i][j] = adj[i][j];
			else
				dist[i][j] = INF;
		}
	}

	for (int k = 1; k <= n; k++) { // Via node
		for (int i = 1; i <= n; i++) { // Start node
			for (int j = 1; j <= n; j++) { // End node
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

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

	return 0;
}