华师一附中OI组

标题: P1744 采购特价商品 [打印本页]

作者: admin 时间: 2018-9-18 16:20
标题: P1744 采购特价商品
题目背景
《爱与愁的故事第三弹·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

作者: admin 时间: 2021-3-21 20:16
比car的旅行路线简单，基本是裸的最短路径，

欢迎光临华师一附中OI组 (http://hsyit.cn/)