百度的一道程序比赛题目，求思路

kestre1

题目描述
北京的一位出租车司机向你抱怨：城市发展太快，公路越来越多，他已经疲于计算行驶路线，于是求助你开发一个自动导航的工具。
出租车只能在公路上行驶。所有的公路都是笔直、双向的，相交的公路视为连通（可以在交叉点处从一条公路开到另一公路上）。由于道路施工，整个城市的公路系统可能并不完全通畅。如果乘客的目的地不在公路边，则乘客下车后要步行前往，步行路线不受公路限制。这位好心的司机还特别提出，乘客步行距离越短越好；其次，出租车行驶里程越短越好。
方便起见，用笛卡尔坐标系来描述城市地图，所有坐标都在第一象限[0, 1000]的范围内。公路宽度忽略不计。
输入格式
第一行是一个数字k，代表公路条数。以下k行每行用4个实数描述一条公路（用空格隔开），前两个表示公路起点，后两个表示公路终点。下一行包含4个实数（用空格隔开），前两个表示乘客上车点，后两个表示乘客目的地坐标。不相交公路间的最短距离至少为10-4。
输出格式
仅一行，为出租车行驶的里程数，保留一位小数。
输出格式
2
2.0 2.0 10.0 10.0
10.0 2.0 2.0 10.0
3.0 3.0 9.0 4.0
输出样例
7.8
评分方法
本题有20组数据，满足k<=100, 公路的交点数不超过10000。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
大家讨论下，小弟对关于图的算法不是很了解，一时没什么好的思路

chinaltang

带权图的 Dijkstra 算法

首先确定乘客在公路上的上车点和下车点（即源点和目的点），然后和所有公路交点纳入一个带权图中（该图可以用矩阵存储），再应用Dijkstra求解。

kestre1

谢谢楼上的，知道思路了好好研究下。

daybreakcx

先算一个直接步行的
然后是经由公路的，先将起点和终点分别化为离他们最近的点（点到直线距离，可能有等距离的，此时就是多起点或者多终点），然后Dijkstra，不过是那些起点每个都算一次，终点任何一个都行，取最小值和直接步行的比取最小
我的思路是这样的，超时应该不会有吧

chinaltang

恩  对题目来说确实存在直接步行的可能性及多起点多终点的情形  我没考虑到这一情形 学习了