[1613번] 역사

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 플로이드 워셜 알고리즘

플로이드로 간단히 해결되는 문제이다.

a->b로 가는 길이 있다면 a가 먼저 나왔다는 의미이고(-1)

b->a로 가는 길이 있다면 b가 먼저 나왔다는 의미이고(1)

둘다 아니라면 서로중 누가 먼저 나온지 모른다는 의미이다(0)

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

#include <iostream> #include <cstdio> #include <queue> #include <algorithm> #include <vector>   using namespace std;   const int INF = 987654321; int adj[402][402];   int main() {     int n, m;     scanf("%d %d", &n, &m);       for (int i = 0; i <= 400; i++)         for (int j = 0; j <= 400; j++)             if(i != j)                 adj[i][j] = INF;       for (int i = 0; i < m; i++)     {         int from, to;         scanf("%d %d", &from, &to);           adj[from][to] = 1;     }       for (int k = 1; k <= n; k++)         for (int x = 1; x <= n; x++)             for (int y = 1; y <= n; y++)                 if (adj[x][y] > adj[x][k] + adj[k][y])                     adj[x][y] = adj[x][k] + adj[k][y];          int t;     scanf("%d", &t);     while (t--)     {         int a, b;         scanf("%d %d", &a, &b);           if (adj[a][b] != INF)             printf("-1\n");         else if (adj[b][a] != INF)             printf("1\n");         else             printf("0\n");     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus