P1744 采购特价商品

    • 710通过
    • 1.7K提交
  • 题目提供者 情到深处人孤独
  • 评测方式 云端评测
  • 标签 SPFA 图论 队列
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    《爱与愁的故事第三弹·shopping》第一章。

    题目描述

    中山路店山店海,成了购物狂爱与愁大神的“不归之路”。中山路上有n(n<=100)家店,每家店的坐标均在-10000~10000之间。其中的m家店之间有通路。若有通路,则表示可以从一家店走到另一家店,通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗?

    输入输出格式

    输入格式:

    共n+m+3行:

    第1行:整数n

    第2行~第n+1行:每行两个整数x和y,描述了一家店的坐标

    第n+2行:整数m

    第n+3行~第n+m+2行:每行描述一条通路,由两个整数i和j组成,表示第i家店和第j家店之间有通路。

    第n+m+3行:两个整数s和t,分别表示原点和目标店

    输出格式:

    仅一行:一个实数(保留两位小数),表示从s到t的最短路径长度。

    输入输出样例

    输入样例#1: 复制
    5
    0 0
    2 0
    2 2
    0 2
    3 1
    5
    1 2
    1 3
    1 4
    2 5
    3 5
    1 5
    输出样例#1: 复制
    3.41

    说明

    100%数据:n<=100,m<=1000

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