백준 11404, 플루이드

문제

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

풀이

그냥 플로드이-워셜 알고리즘을 적용하면 풀리는 문제 였다. 다만 해당 알고리즘을 몰라서 익히고 풀었다. 쉬워서 구현자체는 간단했다.

시간복잡도가 O(N^3) 인 것을 기억하고 사용한 틀을 익히도록 하자.

실수

• 문제를 제대로 안봐서 시간끔 (같은 노선이 중복이 존재할 수 있음
• 쉬운데 시간이 오래 걸린듯

코드

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>

using namespace std;

int n, e;
vector<vector<int>> dp(110, vector<int>(110, 300000000));

int main() {

	int a, b, c;

	scanf("%d %d", &n, &e);

	for (int i = 0; i < e; i++) {

		scanf(" %d %d %d", &a, &b, &c);

		dp[a][b] = min(dp[a][b], c);

	}

	for (int k = 1; k <= n; k++) {

		for (int i = 1; i <= n; i++) {

			for (int j = 1; j <= n; j++) {

				if (i == j)
					dp[i][j] = 0;

				else
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

			}

		}

	}

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= n; j++) {


			if (dp[i][j] == 300000000)
				printf("0 ");

			else 
				printf("%d ", dp[i][j]);

		}

		printf("\n");

	}

	return 0;

}