[백준] 11404 플로이드 C++, python

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

11404번: 플로이드

그래프 탐색 알고리즘중 하나인 floyd-warshall 알고리즘을 사용하는 문제이다. 해당 알고리즘은 dijkstra와 달리 모든점에서 모든점까지의 최소거리를 탐색할때 사용한다. 

floyd warshall 알고리즘을 간단하게 설명하면 (1) s에서 e까지의 거리를 직접 가는 경우(cost[s][e])와 (2) k 점을 거쳐 가는 경우(cost[s][k] + cost[k][e]) 두 개를 비교하면서 둘 중 작은 값으로 갱신(cost[s][e] = min((1),(2)))하면 된다. 자세한건 맨아래 링크 참고.

 

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

void init();
void floyd();
void output();

int n, m;
int cost[100][100] = { 0, };

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	init();
	floyd();
	output();

	return 0;
}
void init() {
	int i, j, a, b, c;
	cin >> n >> m;
	// initialize array
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (i != j)
				cost[i][j] = INF;
		}
	}

	// input cost
	for (i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		if (cost[a - 1][b - 1])
			cost[a - 1][b - 1] = min(cost[a - 1][b - 1], c);
		else
			cost[a - 1][b - 1] = c;
	}
}
void floyd() {
	int i, j, k, tmp;
	for (k = 0; k < n; k++)
	{
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
			}
		}
	}

}
void output() {
	int i, j;
	// post processing and print
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (cost[i][j] == INF)
				cost[i][j] = 0;
			cout << cost[i][j] << ' ';
		}
		cout << '\n';
	}
}

 

이건 파이썬 풀이이고 알고리즘은 똑같다

import sys; input = sys.stdin.readline

def main():
    INF = 987654321
    n, m = int(input()), int(input())
    cost = [[INF for _ in range(n)] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        cost[a][b] = min(cost[a][b], c)
    for i in range(n):
        cost[i][i] = 0

    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    answer = []
    for i in range(n):
        for j in range(n):
            if cost[i][j] == INF:
                cost[i][j] = 0
        answer.append(' '.join(map(str, cost[i])))
    print('\n'.join(answer))

if __name__ == '__main__':
    main()

 

 

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Floyd–Warshall algorithm - Wikipedia