【题26】Car的旅行路线--试题解析.doc

【题26】Car的旅行路线又到暑假了，住在城市A的 Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速公路（图6.2.9）。第i个城市中高速公路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。图6.2.9那么Car应如何安排到城市B的路线才能尽可能的节省花费昵？她发现这并不是一个简单的问题，于是她来向你请教。任务找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。输人文件：键盘输入文件名输 出：到屏幕（输出最小费用，小数点后保留2位。）输入格式第一行为一个正整数n(0n10)，表示有n组测试数据。每组的第一行有四个正整数s，t，A，B。s（0S100）表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，（1A，BS）。接下来有s行，其中第i行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第i个城市中任意三个机场的坐标，Ti为第i个城市高速公路单位里程的价格。输出格式：共有n行，每行一个数据对应测试数据。输入输出样例输入13 10 1 31 1 1 3 3 1 302 5 7 4 5 2 1 8 6 8 8 11 6 3输出47.55题解、 计算两点间的欧氏距离输入信息给出了各城市内高速公路单位里程价格和城市间飞机的单位里程价格。要知道两个机场间的路程费用，必须知道两个机场间的距离。设两个机场的坐标分别为（x1，y1）和（x2，y2）。按照欧氏公式，它们之间的距离应为dist=。我们通过函数dist(x1，y1，x2，y2)计算和返回（x1，y1）和（x2，y2）间的欧氏距离：function dist(x1，y1，x2，y2:integer):real；计算和返回（x1，y1）与（x2，y2）间的欧氏距离begindistsqrt(sqr(x1-x2)+sqr(y1-y2)；end；dist2.计算每个机场的坐标序列 每个城市的四个飞机场分别位于一个矩形的四个顶点上，输入信息仅给出了其中的三个坐标，如何计算第四个机场的坐标。设p1=(x1，y1) p2=(x2，y2) p3=(x3，y3)为某城市的三个机场坐标，要求计算该城市的第四个机场坐标p=(x，y)。显然，p1、p2和p3中必有一条边为矩形边。有三种可能：l （p1，p2）为矩形边。在这种情况下，（p3，p）必为相对的矩形边，且（=）（x1+x2=x3+x）(y1+y2=y3+y)）即 x=x1+x2-x3 y=y1+y2-y3l （p1，p3）为矩形边。在这种情况下，（p2，p）必为相对的矩形边，且（=）（x1+x3=x2+x）(y1+y3=y2+y)）即 x=x1+x3-x2 y=y1+y3-y2l （p2，p3）为矩形边。在这种情况下，（p1，p）必为相对的矩形边，且（=）（x2+x3=x1+x）(y2+y3=y1+y)）即 x=x2+x3-x1 y=y2+y3-y1在上述三种可能性中，必有（且仅有）一种可能性成立。我们按照上述公式依次假设(x，y)的可能值，并代入公式检验，条件成立的(x，y)即为城市的第四个机场坐标。设map为机场序列，该序列含4*n个坐标，其中（mapi*4-3，1，mapi*4-3，2）（map4*i，1，map4*i，1）为城市i的四个机场坐标(1in)。我们在输入测试数据的同时计算map：读城市数n，飞机的单位里程价格t，出发城市序号a，目标城市序号b； for i1 to n do begin 读第i个城市的三个机场坐标(x1，y1)（x2，y2）（x3，y3）和高速公路的单位里程价格fi)； xx1+x2-x3；yy1+y2-y3；假设（p1，p2）和（p3，p）为相对的两条矩形边，计算p坐标 if dist(x1，y1，x2，x2)dist(x3，y3，x，y) then begin若假设不成立，则假设（p1，p3）（p2，p）为相对的两条矩形边，计算p坐标 xx1+x3-x2；yy1+y3-y2； if dist(x1，y1，x3，y3)dist(x2，y2，x，y) 若假设不成立，则假设（p2，p3）（p1，p）为相对的两条矩形边，计算p坐标 then beginxx2+x3-x1；yy2+y3-y1；end；thenend；thenmapi*4-3，1x1；mapi*4-3，2y1； 将矩形的四个顶点坐标存入map数组mapi*4-2，1x2；mapi*4-2，2y2；mapi*4-1，1x3；mapi*4-1，2y3；mapi*4，1x；mapi*4，2y；end；for3.使用Dijkstra算法计算最小费用按照Dijkstra算法的思想，将所有机场分为两组 第一组：包括已确定最小费用的机场；第二组：包括尚未确定最小费用的机场；设used为机场的分组标志。其中usedi=ans为第一组机场的最小费用序列。其中ansi为出发城市至第一组中机场i的最小费用（1i4*n）我们按最小费用递增的顺序把第二组的机场加到第一组中去，直至到达目标城市b中的任一个机场为止。在这个过程中，总保持从出发城市a到第一组各机场的最小费用都不大于从a至第二组任何机场的费用。另外，每一个机场对应一个费用值。第一组机场对应的费用值就是由a到此机场的最小费用；第二组机场对应的费用值就是a经由第一组机场（中间机场）至此机场的最小费用。具体作法是： 初始时，出发城市a的四个机场进入第一组（useda*4-3、useda*4-2、useda*4-1、useda*4设为true）；所有机场的费用值为0；第二组包含其它所有机场。然后每次从第二组中选一个机场mi加到第一组中。这个机场必须满足如下条件：1. 出发城市a经由第一组的某机场i(usedi=true)可直达mi机场；2. 其费用（ansi+机场i至机场mi的直接费用）在第二组机场的所有费用中是最小的；机场i至机场mi使用的交通工具不同，直接费用亦随之不同。问题是机场i至机场mi究竟使用哪一种交通工具。这取决于两个机场所属城市的关系： 机场i所属的城市为now=。若机场mi在城市now（4*now-3mi4*now），则从机场i坐火车至机场mi；若机场mi在其他城市（1mi4*now-4，4*now+1mi4*n）,则从机场i坐飞机至机场mi。按照上述规律依次往第一组加入一个机场mi，直至被加入的机场mi属于目标城市b为止（4*b-3mi4*b）。由此得出算法： procedure solve；varused :array1.4*maxn of boolean； 第一组的机场标志min，u:real； 目前为止的最小费用为min，当前方案的费用为umi，i，j，now:integer； 被加入第一组的机场序号为mi，机场所在的城市序号为nowbeginif a=b 若出发城市即为目标城市，则输出最小费用为0，并退出程序then beginwriteln(0)；exit；end；thenfillchar(used，sizeof(used)，false)；初始时所有机场在第二组，该组内所有机场的最小费用为0fillchar(ans，sizeof(ans)，0)；useda*4-1true； 出发城市a的四个机场进入第一组useda*4-2true；useda*4-3true；useda*4true；repeatminmaxint； 最小费用初始化for i1 to 4*n do 搜索第一组内的每一个机场if usedi then beginnow(i-1) div 4 +1； 计算机场i所在的城市序号for j1 to 4*now-4 do 搜索第二组内城市1城市now-1的每一个机场jif not usedj then begin 计算出发城市至机场i，然后坐飞机至机场j的最小费用 uansi+dist(mapj，1，mapj，2，mapi，1，mapi，2)*t； if umin 若该费用为最小，则记下最小费用和去往城市then begin minu；mij；end；then end；thenfor j4*now-3 to 4*now do 搜索第二组内城市now的每一个机场j if not usedj then begin 计算出发城市至机场i，然后坐火车至机场j的最小费用 uansi+dist(mapj，1，mapj，2，mapi，1，mapi，2)*fnow； if umin 若该费用为最小，则记下最小费用和去往城市then begin minu；mij；end；then end；thenfor j4*now+1 to 4*n do 搜索第二组内城市now+1城市n的每一个机场jif not usedj then begin 计算出发城市至机场i，然后坐飞机至机场j的最小费用 uansi+dist(mapj，1，mapj，2，mapi，1，mapi，2)*t； if umin 若该费用为最小，则记下最小费用和去往城市then begin minu；mij；end；then end；then end；thenif mi in 4*b-3.4*b 若到达目标城市的一个机场，则输出最小费用并退出程序then begin wri