[백준] 1719 - 택배

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

1719번: 택배

 

n 제한이 200이므로 플로이드-와샬 알고리즘을 통해 최단 거리를 구할 수 있다.

그러면 최단 경로는 어떻게 구해야 할까?

 

플로이드-와샬 알고리즘을 살펴보면,

for(int k = 0; k < n; k++) {
	for(int i = 0; i < n; i++) {
    	for(int j = 0; j < n; j++) {
        	//가중치가 최소일 때 업데이트
        }
    }
}

 

이러한 형태로 구현된다.

i, j, k가 의미하는 바는, i 정점에서 j 정점으로 갈 때 k 정점을 지나는 경로를 뜻한다.

즉 가중치가 최소, 업데이트 시점에 i에서 j로 가는 정점은 k 정점을 지나야 한다는 뜻이다.

따라서 이때 구하려는 답 또한 업데이트된다.

 

#include <iostream>
#include <vector>
using namespace std;

int n, m;
int board[201][201], inp[201][201];

int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
        
		board[a][b] = board[b][a] = c;
		inp[a][b] = b;
		inp[b][a] = a;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
            
				if (i == j)continue;
                
				if (board[i][k] && board[k][j]) {
					if (board[i][j] == 0 || board[i][j] > board[i][k] + board[k][j]) {
                    
						board[i][j] = board[i][k] + board[k][j];
                        
						if (i != k) {
							inp[i][j] = inp[i][k];
						}
					}
				}
			}
		}
	}

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