(C++) - 백준(BOJ) 11265번 : 끝나지 않는 파티

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

11265번: 끝나지 않는 파티

floyd warshell문제였습니다.

 

 

📕 풀이방법

O(n^3)의 시간복잡도를 가지기 때문에 효율적이지는 않으나 n이 적절히 작을 경우 구현이 간편하기 때문에 자주 사용합니다.

 

📔 입력 및 초기화

 인접그래프를 party라는 이 차원 배열에 입력받습니다. 이후 n, m만큼 적절히 입력받습니다. m만큼 각각 a,b,c를 입력했다면 party[a][b]는 a에서 b로 갈 때 걸리는 최소시간입니다.

 

📔 풀이과정

 floyd warshell로 i -> k + k -> j로 가는 비용이 i -> j로 가는 비용보다 작은 경우 i -> j로 가는 비용을 갱신해줍니다.

 

📔 정답출력

 party[a][b] <= c라면 "Enjoy other party"를 아니라면 "Stay here"를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int party[501][501], n, m;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> party[i][j];
        }
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(party[i][k] + party[k][j] < party[i][j]){
                    party[i][j] = party[i][k] + party[k][j];
                }
            }
        }
    }
    
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        if(party[a][b] <= c) cout << "Enjoy other party\n";
        else cout << "Stay here\n";
    }
}