P3831 [SHOI2012]回家的路

    • 71通过
    • 191提交
  • 题目提供者 chen_zhe 管理员
  • 评测方式 云端评测
  • 标签 SPFA 图论 最短路 各省省选 2012 上海 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    SHOI2012 D2T1

    题目描述

    2046 年 OI 城的城市轨道交通建设终于全部竣工,由于前期规划周密,建成后的轨道交通网络由 $2n$ 条地铁线路构成,组成了一个 $n$ 纵 $n$ 横的交通网。如下图所示,这 $2n$ 条线路每条线路都包含 $n$ 个车站,而每个车站都在一组纵横线路的交汇处。

    出于建设成本的考虑,并非每个车站都能够进行站内换乘,能够进行站内换乘的地铁站共有 $m$ 个,在下图中,标上方块标记的车站为换乘车站。已知地铁运行 1 站需要 2 分钟,而站内换乘需要步行 1 分钟。Serenade 想要知道,在不中途出站的前提下,他从学校回家最快需要多少时间(等车时间忽略不计)。

    输入输出格式

    输入格式:

    第一行有两个整数 $n,m$ 。

    接下去 $m$ 行每行两个整数 $x,y$ ,表示第 $x$ 条横向线路与第 $y$ 条纵向线路的交

    汇站是站内换乘站。

    接下去一行是四个整数 $x_1,y_1,x_2,y_2$ 。表示 Serenade 从学校回家时,在第 $x_1$ 条横向线路与第 $y_1$ 条纵向线路的交汇站上车,在第 $x_2$ 条横向线路与第 $y_2$ 条纵向线路的交汇站下车。

    输出格式:

    输出文件只有一行,即 Serenade 在合理选择线路的情况下,回家所需要的时间。如果 Serenade 无法在不出站换乘的情况下回家,请输出-1。

    输入输出样例

    输入样例#1: 复制
    2 1
    1 2
    1 1 2 2
    输出样例#1: 复制
    5
    输入样例#2: 复制
    6 9
    2 1
    2 5
    3 2
    4 4
    5 2
    5 6
    6 1
    6 3
    6 4
    1 1 4 6
    输出样例#2: 复制
    27
    输入样例#3: 复制
    6 10
    2 1
    2 5
    3 2
    4 4
    5 2
    5 6
    6 1
    6 3
    6 4
    6 6
    1 1 4 6
    输出样例#3: 复制
    26

    说明

    对于 30%的数据, $n\le 50,m\le 1000$ ;

    对于 60%的数据, $n\le 500,m\le 2000$ ;

    对于 100%的数据, $n\le 20000,m\le 100000$ ;

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