[BOJ 1613] 역사

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

일의 우선순위를 물어보는 역사시간 문제이다 ㅋㅋ 처음 문제를 보고 접근방법으로 위상정렬로 하려고 했는데 .... 이게 왠건 플로이드 워셜이네 ....

(어떤부분을 보고 플로이드 워셜로 접근하는 사람들이 있는지 궁금하긴 하다)

일단 플로이드로 구현하게 된다면 각각의 가중치를 두고 플로이드를 돌린 후 일정 조건에 따라 다르게 출력해주면 된다. 

#include <iostream>
#include <cstdio>
#include <cstring>
#define  INF 1000000000
using namespace std;
 
int n,m,arr[411][411],t;
int a,b;
int main(){
    scanf("%d%d" , &n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            arr[i][j] = INF;
        }
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d" , &a,&b);
        arr[a][b] = 1;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                arr[i][j] = min(arr[i][j] , arr[i][k]+arr[k][j]);
            }
        }
    }
    scanf("%d" , &t);
    while(t--){
        scanf("%d%d" , &a,&b);
        if(arr[a][b] == INF && arr[b][a] == INF){
            printf("0\n");
        }else if(arr[a][b] != INF&& arr[a][b] > 0){
            printf("-1\n");
        }else {
            printf("1\n");
        }
    }
    return 0;
}