백준1719 - 택배

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

1719번: 택배

M대 M으로 최소거리 찾는 방법이여서 플로이드 와샬을 선택했다. 입력받는 지점의 출발점을 지정해 두었다가 최소거리가 갱신되면 갱신된 지점의 출발점으로 현재 출발점을 바꾸는 방식을 택했다.

#include <iostream>
#define INF 100000000;
#define MAX 201
using namespace std;

int n, m; //n은 마을 수, m은 경로수
int a, b, c; //a -> b로 가면 c가 든다.
int d[MAX][MAX]; //플로이드 와샬의 결과를 담는 공간
int start[MAX][MAX]; //시작하는 지점을 담는 공간

//처음에 플로이드 와샬을 실행할 공간을 INF로 초기화, 자신 스스로 들어가는 곳은 0으로 초기화
void setting() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			if (i == j) {
				d[i][j] = 0;
			}
			else {
				d[i][j] = INF;
			}
		}
	}
}

//프로이드 와샬을 수행하는 함수
void floydwashall() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (d[i][j] > d[i][k] + d[k][j]) { //현재 비용보다 새로운 비용이 더 크면
					d[i][j] = d[i][k] + d[k][j]; //현재 비용을 갱신한다.
					start[i][j] = start[i][k]; //출발지점을 바꾼다.
				}
			}
		}
	}
}

int main() {
	setting(); //플로이드 와샬 공간 초기화

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		d[a][b] = c;
		d[b][a] = c;
		start[a][b] = b; //시작점 설정
		start[b][a] = a; //시작점 설정
	}

	floydwashall();

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