[BOJ] 11265번 : 끝나지 않는 파티 C++ 풀이

각 노드간의 거리가 주어졌을때, A -> B로 이동하는 최소 시간이 C보다 작거나 같은지 확인하는 문제이다.

노드의 개수가 500개, 쿼리의 개수가 1만개이다. 
노드의 개수를 N, 쿼리의 개수를 K라고 하자. 그렇다면 간선의 개수는 N^2개가 되는 것을 알 수 있다.
쿼리가 들어올때마다 다익스트라를 돌리면 O(KN^2 log N)의 시간복잡도가 소요되기에 시간안에 문제를 해결할 수 없다. 따라서 N이 작은 것을 이용하면 되는데, 플로이드 와샬을 사용하면 된다는 것을 눈치챌  수 있다.

O(N^3)에 모든 노드간의 거리를 전처리 해놓는다면 쿼리를 해결하는데 O(1)의 시간복잡도가 걸린다. 따라서 O(N^3)에 문제를 해결할 수 있다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 1000000000
#define MOD 1000000009
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
int N, M, visited[510][510];

void ployd() {
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            for (int k=1; k<=N; k++) {
                visited[j][k] = min(visited[j][k], visited[j][i] + visited[i][k]);
            }
        }
    }
}

void init() {
    cin >> N >> M;
    for (int i=1; i<=N; i++) for(int j=1; j<=N; j++) visited[i][j] = INF;
    for (int i=1; i<=N; i++) for(int j=1; j<=N; j++) cin >> visited[i][j];
    ployd();
    for (int i=1; i<=M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (visited[a][b] <= c) {
            cout << "Enjoy other party" << '\n';
        } else {
            cout << "Stay here" << '\n';
        }
    }
} 

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