P3632 [APIO2011]寻路

    • 67通过
    • 171提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 SPFA 最短路 模拟 APIO 2011 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    TooDee 是一块二维格子状的土地(就像著名的笛卡尔坐标系那样),在这里生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物,它们只在二维活动,而且他们非常的 文明开化。TooDee的蜂窝和正常世界的蜂窝也是很不一样的,他们是矩形的且它们的边平行于TooDee的地理坐标系,就是说矩形的边或者是东西走向, 或者是南北走向。

    因为Dees是很高级的生物,他们有很多固定的飞行轨道,这些轨道由一些平行于坐标轴的线段组成,线段只会在经纬度都是整数的点相交。Dee在TooDee飞行时必须遵守以下规则(请记住TooDee中所有点的经纬度都是整数):

    一、如果当前在点(X, Y),则下一步只能飞到四个邻点(X, Y - 1),(X, Y + 1),(X - 1, Y),(X + 1, Y);

    二、不可以进入蜂巢;

    三、只能在蜂巢的角上或者边上改变飞行方向;

    四、开始的时候可以向任何方向飞;

    今晚是公共财政大臣Deeficer的女儿的生日,她想尽早回家,请帮她找到最快的回家路径。假设她每秒可以飞行一个单位的距离。

    输入输出格式

    输入格式:

    每个测试点包含多组数据。

    输入的第一行包含一个整数T,表示测试数据的组数。接下来依次描述这T组数据,相邻的两组之间使用一个空行分隔,测试数据不多于20组。

    对 于每组数据,第一行包含四个整数x[s],y[s],x[t],y[t],表示Deeficer的办公室和家的坐标分别是(x[s], y[s])和(x[t], y[t])。第二行包含一个整数n,表示蜂巢的个数。接下来的n行描述所有的蜂巢,其中第i行包含四个整数 x[i1],y[i1],x[i2],y[i2],表示第i个蜂巢两个对角的坐标分别为(x[i1], y[i1])和(x[i2], y[i2])。

    任何两个蜂巢不会相交,也不会接触(在角上也不会接触)。办公室和家处在不同的位置。每个蜂巢的面积为正。

    输出格式:

    对于每一组数据,输出一个整数,表示Deeficer最快回家的时间(单位为秒),如果她无法按规则回家,则输出“No Path”。

    输入输出样例

    输入样例#1: 复制
    2
    1 7 7 8
    2
    2 5 3 8
    4 10 6 7
    2 1 5 4
    1
    3 1 4 3
    输出样例#1: 复制
    9
    No Path

    说明

    对于20%的测试数据,n<=10,所有的坐标都是小于100的非负整数;

    对于60%的测试数据,n<=100,所有坐标的绝对值都小于1000;

    对于100%的测试数据,0<=n<=1000,所有坐标的绝对值都是不超过10^9的整数。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。