www.acmicpc.net/problem/14588
#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;
}
댓글