백준 1613 역사 - C++

1613번: 역사

#include <iostream>
#include <vector>
using namespace std;

int n, k, s, from, to;
int pre, aft;
int history[401][401];
vector<pair<int, int>> sol;

void History(){
    for(int v = 1; v <= n; v++){
        for(int f = 1; f <= n; f++){
            for(int t = 1; t <= n; t++){
                if(!history[f][t]){
                    if(history[f][v] == 1 && history[v][t] == 1)
                        history[f][t] = 1;
                    else if(history[f][v] == -1 && history[v][t] == -1)
                        history[f][t] = -1;
                }
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &k);
    while(k--){
        scanf("%d %d", &pre, &aft);
        history[pre][aft] = -1;
        history[aft][pre] = 1;
    }

    scanf("%d", &s);
    while(s--){
        scanf("%d %d", &from, &to);
        sol.push_back(make_pair(from, to));
    }

    History();

    for(int i = 0; i < sol.size(); i++)
        printf("%d\n", history[sol[i].first][sol[i].second]);
}

---

 전 경로를 구해야 하고 n이 400이니 플로이드-와샬 알고리즘을 이용해서 풀이하게 됩니다. 문제대로 history[i][j]에서 i가 j 보다 먼저 일어난 사건이라고 하면 -1, 나중에 일어난 사건이라고 하면 1이라고 저장하고 문제를 풀이하면 됩니다.

 이전 사건과 이후 사건의 앞뒤가 구해진다고 하면 플로이드-와샬처럼 중간 경유지를 넣어서 배열을 업데이트 해주면 됩니다.