P2083 找人

    • 169通过
    • 449提交
  • 题目提供者 R3974840
  • 评测方式 云端评测
  • 标签 搜索 树形结构 洛谷原创
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    题目描述

    小明要到他的同学家玩,可他只知道他住在某一单元,却不知住在哪个房间。那个单元有N层(1,2……N),每层有M(1,2……M)个房间。

    小明会从第一层的某个房间开始找,他找的方式也很特别,每次到了一个房间,如果不是他的同学,他就会询问这人,

    然后他就会去那人告诉他的房间号,如果还不是,他就会继续按这个方法找下去,直到找到。当然,他也有可能找不到同学。他的体力也是有限的,他每爬一层楼梯就会消耗V体力值。你的任务就是求找到同学耗费的最少体力值,如果找不到,就输出impossible 。

    输入输出格式

    输入格式:

    共N+1行。

    第一行,N,M,V,X,Y(X,Y表示同学只在X层Y房间)

    2~N+1行,每行M*2个数字,第i+1行j*2-1个数Ak和j*2个数Ak+1表示住在i层j房间的人提供的信息是Ak层和Ak+1房间。(同学的信息就是自己的房间号)

    输出格式:

    一个数,即答案。

    输入输出样例

    输入样例#1: 复制
    3 3 2 2 3
    1 3 3 3 2 1
    2 3 1 1 2 3
    1 1 1 2 2 3
    
    输出样例#1: 复制
    2

    说明

    N<=1000,M<=100,V<=50

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