跳至正文
题库4246
#4246

Car的旅行路线

查看题目操作

Car的旅行路线

题目描述

又到暑假了,住在城市 A 的 Car 想和朋友一起去城市 B 旅游。每个城市都有四个机场,分别位于一个矩形的四个顶点。

同一城市的任意两个机场之间都有笔直的高速铁路,第 i 个城市铁路的单位里程价格为 T_i。不同城市的任意两个机场之间都有航线,航线的单位里程价格均为 t。铁路和航线都可以双向乘坐,路程为两个机场之间的直线距离。

可以选择城市 A 的任意机场出发,并在城市 B 的任意机场结束,中途也可以经过其他城市。求最小总花费。如果 A = B,可以直接结束旅程,花费为 0。

输入格式

输入只有一组数据。第一行四个正整数 S、t、A、B,依次表示城市数、航线单位里程价格、出发城市编号和到达城市编号。1 ≤ A, B ≤ S。

接下来 S 行,每行七个正整数 x_i1、y_i1、x_i2、y_i2、x_i3、y_i3、T_i。前三对坐标是第 i 个城市任意三个不同机场的位置,它们构成同一个非退化矩形的三个顶点;第四个机场的位置可由它们确定。T_i 是该城市铁路的单位里程价格。

输出格式

输出一行,表示最小总花费,保留一位小数。

样例

3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3
47.5
1 10 1 1
1 1 2 2 2 1 10
0.0

数据范围

1 ≤ S ≤ 100。

来源

蓝桥杯 算法训练