백준1238 - 파티

 

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

1238번: 파티

N명의 사람들이 X번의 마을에서 파티가 있어 파티에 참여한다.

파티에 참여 후 집까지 돌아가는 시간을 계산한다.

가장 집까지 돌아가는데 시간이 오래걸린 사람을 찾아서 그 사람이 걸린 시간을 출력한다.

 

처음에는 다익스트라 알고리즘을 사용했다.

하지만 다익스트라는 일 대 다의 관계에서 사용하는 것이 효율적인 알고리즘이기 때문에 다 대 다의 관계에서 효율적인 플루이드와샬알고리즘을 사용하였다.

 

#include <iostream>
#include <string.h>
#define INF 10000000
using namespace std;

int N, M, X; //N은 사람수, M은 입력하는 횟수, X는 마을의 번호
int mat[1001][1001]; //한 마을에서 다른 마을로 가는 시간
int d[1001][1001]; //플루이드 와샬 알고리즘을 수행한 결과

void FloydWarshall() {
	//mat에 입력한 것들을 플루이드 와샬 알고리즘 수행한 결과를 담을 변수에 넣는다.
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			d[i][j] = mat[i][j];
		}
	}

	//k를 거쳐갈 때와 거쳐가지 않을 때를 비교하여 짧은 거리를 갱신한다.
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (d[i][k] + d[k][j] < d[i][j]) {
					d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
	}
}


int main() {
	int max = -1;

	cin >> N >> M >> X; 

	//비어있는 칸을 INF로 초기화하는데 같은 행과 열은 0으로 초기화 한다.
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) {
				mat[i][j] = 0;
			}
			else {
				mat[i][j] = INF;
			}
		}
	}

	while (M--) {
		int a, b, c; //a는 출발하는 마을, b는 도착하는 마을, c는 걸리는 시간
		cin >> a >> b >> c;
		mat[a][b] = c; //a -> b로 가는데 c시간이 걸린다.
	}

	FloydWarshall();

	//X번 마을을 들렸다가 다시 자기의 마을을 돌아가는 경우 가장 오래 걸린 시간을 찾는다.
	for (int i = 1; i <= N; i++) {
		if (max < d[i][X] + d[X][i]) {
			max = d[i][X] + d[X][i];
		}
	}

	cout << max;
}