沙龙之《Car的旅行路线》解题报告
   
　　　　　　　　　　　　　　　　　　　　　　　　福州一中 石淙寅

　　这是一道典型的与图论有关的题目，用到的算法只有一个，就是Dijkstra单源最短路径算法。此题的技巧在于如何判断矩形的第四个顶点。由于输入文件中已经提供了矩形的三个顶点，要判断矩形的第四的顶点，就要首先判断这三个点的关系。

　　（１） 首先判断直角的位置：
　　因为从测试数据文件中读入的三个点的坐标是无序的，因此需判断直角的位置，然后在计算第四个点的坐标。如图，对于线段L1、L2，如果（x1-x2）*（x3-x2）+（y1-y2）*（y3-y2）＝0，那么L1 ⊥ L2。
　　（２） 计算（x4，y4）:
　　如图：由x4-x3＝x1-x2得x4＝x1-x2+x3，同样的y4＝y1-y2+y3
　　（３） 用邻接表或邻接矩阵把各个（机场）点之间的连接关系表示出来。
　　（４） 计算各条高速铁路的长度l，并求出每个城市中每条高速铁路的总价：Ti * l
　　（５） 计算各条飞机航线的长度l'，并求出每条航线的总价：t * l'
　　用Dijkstra计算各点间的最短路径，求出费用最少的路线。

　　DIJKSTRA算法算法思想：
　　设置一个顶点集合S并不断地作贪心选择来扩大这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。DIJKSTRA算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中的顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。

　　参考程序：

　　
　　
　　
　　
　　
　　
　
　


    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有