[백준 14588] Line Friends (Small)

www.acmicpc.net/problem/14588

14588번: Line Friends (Small)

#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAX 1e9

using namespace std;
struct s
{
  int left, right;
};

int n, l, r, q, a, b;
s arr[301];
int dis[301][301];

bool check(int a, int b)
{
  if (arr[a].right < arr[b].left || arr[b].right < arr[a].left)
  {
    return 0;
  }
  return 1;
}
int main(void)
{
  fill(&dis[0][0], &dis[300][301], MAX);
  scanf("%d", &n);

  for (int i = 1; i <= n; i++)
  {
    scanf("%d%d", &l, &r);
    arr[i] = {l, r};
    dis[i][i] = 0;
  }

  for (int i = 1; i < n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      if (i == j)
        continue;
      if (check(i, j))
      {
        dis[i][j] = dis[j][i] = 1;
      }
    }
  }

  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      for (int k = 1; k <= n; k++)
      {
        dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
      }
    }
  }

  scanf("%d", &q);
  vector<int> res;
  while (q--)
  {
    scanf("%d%d", &a, &b);
    if (dis[a][b] == MAX)
    {
      res.push_back(-1);
    }
    else
    {
      res.push_back(dis[a][b]);
    }
  }

  for (auto a : res)
  {
    printf("%d\n", a);
  }

  return 0;
}