[C++] BOJ(백준) 11265 끝나지 않는 파티

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

11265번: 끝나지 않는 파티

 

최단 경로 문제다.

 

플로이드 워셜을 이용하여 풀었다.

이 문제의 입력은 (시작, 끝, 가중치)가 아닌 배열로 입력이 들어오기 때문에 편했다.

플로이드 워셜을 이용해 모든 지점에서 모든 지점까지의 최단 경로를 구한다.

m개의 입력을 맏아 a에서 b까지 걸리는 시간이 c초과와 이하인 경우로 나눠 출력을 한다.

 

#include <iostream>
using namespace std;

int n, m;
int arr[501][501];
int result[51];

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) cin >> arr[i][j];

	for (int i = 1; i <= n; i++) {
		for (int r = 1; r <= n; r++) {
			for (int c = 1; c <= n; c++) {
				arr[r][c] = min(arr[r][c], arr[r][i] + arr[i][c]);
			}
		}
	}

	while (m--) {
		int a, b, c;	cin >> a >> b >> c;
		if (arr[a][b] > c) cout << "Stay here\n";
		else cout << "Enjoy other party\n";
	}
}