# 11265. 끝나지 않는 파티

관련 알고리즘 : 플로이드 와샬

 

문제 링크 : https://www.acmicpc.net/problem/11265

11265번: 끝나지 않는 파티

---

해결 과정

 

문제의 조건들이 눈에 잘 들어오지 않아 정리를 해 보면,

 

<문제 조건>

• 직접 연결 일방통행 통로보다 시간이 '덜' 걸리는 경유 노선 존재 가능
• 파티장 크기 N(5<=N<=500)
• 서비스 요청 손님 수 M(1 ≤ M ≤ 10,000)
• N개의 줄에서, 각 줄의 j번째 수 => (현재 있는 줄의 번째수)의 파티장에서 (j)번째 파티장까지 이동시간
• M개의 줄에서, 세 정수 A, B, C => 손님이 현재 위치한 파티장 번호/ 다음 파티 열리는 파티장 번호 / 다음 파티가 열리기까지 남은 시간

즉, 파티장(정점)에서 다른 파티장(또다른 정점)으로 이동할 때의 최단 경로(여기서는 최단 시간이 최단경로)를 구해야 하므로,

플로이드 와샬 알고리즘을 이용하는 전형적인 문제임을 알 수 있다.

 

플로이드 와샬 참고 링크 : https://blog.naver.com/ndb796/221234427842

 

3중 for문을 통해 모든 정점에서 다른 모든 정점으로 갈 때의 최단 시간을 갖는 경로를 찾고,

min함수를 통하여 다른 정점을 거쳐갈 때와 일방통행 통로를 지나갈 때의 시간을 비교한다.

그리고 그 결과값들을 이용하여 최종 출력 시 C보다 적게 걸리는 시간을 갖는 경로가 있다면 Enjoy other party를 출력한다.

---

C++ 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n; // 파티장 크기
int m; // 손님 수
int way[501][501]; // way[i][j] : i에서 j 파티장으로 가는데 걸리는 시간

void Floyd() // 플로이드 와샬 이용
{
	for (int k = 1; k <= n; k++) 
    {
		for (int i = 1; i <= n; i++) 
        {
			for (int j = 1; j <= n; j++) 
            {
            	// 모든 경로에 대한 최소시간 경로 찾기
				way[i][j] = min(way[i][k] + way[k][j], way[i][j]);
			}
		}
	}
}

void Print()
{
	for (int i = 0; i < m; i++) 
    {
		int a, b, c; // 손님 현재 위치 파티장번호, 다음 파티장 번호, 다음 파티 열릴때까지 남은 시간
		cin >> a >> b >> c;
		if (way[a][b] <= c) // 다음 파티 열리기 전까지 도착 가능한 경로가 있을 시,
        {
			cout << "Enjoy other party\n";
		}
		else 
        {
			cout << "Stay here\n";
		}
	}
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    
	cin >> n >> m;
	for (int i = 1; i <= n; i++) // 시간 입력받기
    {
		for (int j = 1; j <= n; j++) 
        {
			cin >> way[i][j];
		}
	}

	Floyd();
	Print();

	return 0;
}