백준 11404 - 플로이드(복습, C++)

문제 링크입니다. https://www.acmicpc.net/problem/11404

11404번: 플로이드

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

플로이드 와샬 알고리즘을 모르시는 분은 https://dongdd.tistory.com/107 를 참고해주세요

Floyd-Warshall(플로이드 와샬) 알고리즘

 

플로이드 와샬 알고리즘을 사용하면 쉽게 풀 수 있습니다.

주의할 점은, 연결된 선과 비용이 주어졌을 때, 이미 주어졌던 값이라면 두 값을 비교해 최솟값을 넣어주고 시작해야했습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#define INF 987654321

using namespace std;

int N, M;
int dp[101][101]; // [X][Y]일때, X -> Y로 가는 최소값

void reset_map() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dp[i][j] = INF;
		}
	}
}

void floyd_warshall() {
	for (int i = 1; i <= N; i++) { // i를 경유할 경우
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) { // j에서 k로 갈 때
				if (dp[i][k] != INF && dp[j][i] != INF && j != k) {
					dp[j][k] = min(dp[j][k], dp[i][k] + dp[j][i]);
				}
			}
		}
	}
}

void solve() {
	floyd_warshall();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (dp[i][j] == INF) cout << "0" << " ";
			else cout << dp[i][j] << " ";
		}
		cout << "\n";
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	reset_map();
	for (int i = 0; i < M; i++) {
		int x, y, cost;
		cin >> x >> y >> cost;
		if (dp[x][y] != INF) dp[x][y] = min(dp[x][y], cost);
		else dp[x][y] = cost;
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요