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

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

11265번: 끝나지 않는 파티

---

Solved By: Floyd-Warshall

 

A -> B로 가는 일방통행 도로가 있지만 다른 파티장을 경유하여 더 빠르게 갈 수 있는 경로가 있을 수 있다. 최단 경로 알고리즘을 요구한다.

 

그리고, 쿼리에서는 from 노드와 to노드가 매번 달라지므로 Dijkstra 같은 알고리즘을 써서는 매번 from노드로부터 Dijkstra를 돌릴 수는 없다.

 

그렇기 때문에 N의 범위도 1 <= N <= 500 이므로 Floyd-Warshall을 사용하여 돌린 다음 각 쿼리마다 최단 경로 값이 주어진 값보다 작은지 큰지를 판단할 수 있다.

#include <iostream>
#define INF 1e9
#define MAX 501
using namespace std;

int graph[MAX][MAX];
int n, m;

void floydWarshall(){
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(graph[i][k] == INF || graph[k][j] == INF) continue;
                if(graph[i][k] + graph[k][j] < graph[i][j]){
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

int main(){
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            graph[i][j] = INF;
        }
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> graph[i][j];
        }
    }
    
    floydWarshall();
    
    for(int i = 0; i < m; i++){
        int v, u, w; cin >> v >> u >> w;
        if(graph[v][u] <= w){
            cout << "Enjoy other party";
        }
        else{
            cout << "Stay here";
        }
        cout << '\n';
    }
    return 0;
}