百度之星算法题目，高手们都来讨论吧，附上我的解答

题目如下

1. 好心的出租车司机
北京的一位出租车司机向你抱怨：城市发展太快，公路越来越多，他已经疲于计算行驶路线，于是求你开发一个自动导航的工具。
出租车只能在公路上行驶。所有的公路都是笔直、双向的，相交的公路视为连通（可以在交叉点处从一条公路开到另一公路上）。由于道路施工，整个城市的公路系统可能并不完全通畅。如果乘客的目的地不在公路边，则乘客下车后要步行前往，步行路线不受公路限制。这位好心的司机还特别提出，乘客步行距离越短越好；其次，出租车行驶里程越短越好。
方便起见，用笛卡儿坐标系来描述城市地图，所有坐标都在第一象限[0, 10000]的范围内。公路宽度忽略不计。
输入格式
第一行是一个正整数k，代表公路条数。以下k行每行用4个非负整数描述一条公路（用空格隔开），前两个表示公路起点的坐标，后两个表示公路终点的坐标。下一行包含4个非负整数（用空格隔开），前两个表示乘客出发点（保证在某条公路上），后两个表示乘客目的地坐标。乘客必须在出发点上车，中途不换车。任意两条公路最多只有一个公共点。
输出格式
仅一行，为出租车行驶的里程数，保留一位小数（四舍五入）。
输入样例 例


2
2 2 10 10
10 2 2 10
3 3 9 4
输出样例 例
7.8
评分规则
1. 程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过1秒，否则该用例不得分；
2. 要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
3. 本题包含20个测试点，前10组满足k<=10，后10组满足k<=50。每个测试点10分，共200分。

下面是我的解答：
   思路如下，首先输入的公路数据可以看成若干条线段，然后可以求出这些线段的交点，后面还有起点和终点坐标，起点坐标一定在这些线段上，所以可以将起点坐标点和这些线段的交点构成一个图，接下来就是终点坐标，由于终点坐标不一定在这些线段上，如果不在的话可以求出终点坐标到这些线段最短距离的那个点，然后将那个点也构建到图中，这样原问题就变成了求起点和刚才那个点最短路径的问题。这是我的思路，附上代码，高手们检查下有没有问题

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

//对角线最大长度(估算)
const double MAXDIS = 15000;

//代表一个点
class Point{
public:
	double x,y;
	Point(double xa,double ya):x(xa),y(ya){}
	Point(){}
};


class Path{
public:
	double distance;
	Point pt;
};

//代表一条公路 也就是一条线段
class Line{
public:
	Point start;
	Point end;
	Line(Point s,Point e):start(s),end(e){}
	Line(){}

	//判断指定的点是否在本线段上
	bool onLine(Point pt){
		
		if(fabs((end.y - pt.y) * (start.x - pt.x) 
			- (start.y - pt.y) * (end.x - pt.x)) < 0.000001){
			return true;
		}
		else{
			return false;
		}
	}

	//计算线段到指定点的最短距离
	Path shortestDistance(Point pt){
		Path path;
		double s;
		double d1,d2,d3;
		double s1,s2,s3;
		double retval,temp;

		s1 = (start.x - pt.x) * (start.x - pt.x) + (start.y - pt.y) 
					* (start.y - pt.y);
		s2 = (end.x - pt.x) * (end.x - pt.x) + (end.y - pt.y)
					* (end.y - pt.y);
		s3 = (start.x - end.x) * (start.x - end.x) +
					(start.y - end.y) * (start.y - end.y);
		d1 = sqrt(s1);
		d2 = sqrt(s2);
		d3 = sqrt(s3);
		if((d1 + d2) == d3){
			path.distance = 0;
			path.pt = pt;
		}else if((d1 + d3) == d2){
			path.distance = d1;
			path.pt = start;
		}else if((d2 + d3) == d1){
			path.distance = d2;
			path.pt = end;
		}else if((s1 + s3) < s2){
			path.distance = d1;
			path.pt = start;
		}else if((s2 + s3) < s1){
			path.distance = d2;
			path.pt = end;
		}else{
			temp = (d1 + d2 + d3) / 2;
			s = sqrt(temp * (temp - d1) * (temp - d2) * (temp - d3));
			path.distance = (2 * s) / d3;
			int k = (end.y - start.y) / (end.x - start.x);
			path.pt.x= (k * k * start.x + k * (pt.y - start.y) + pt.x)/(k * k+1);
			path.pt.y=k * (path.pt.x - start.x) + start.y;
		}
		return path;
	}

	//计算两线段间的焦点
	Point calcPoint(Line line){
		Point pt(-1,-1);
		double k1,k2,b1,b2;
		bool lim1 = false,lim2 = false;
		if(start.x != end.x){
			k1 = (end.y - start.y) / (end.x - start.x);
			b1 = start.y - k1 * start.x;
		}else{
			lim1 = true;
		}

		if(line.start.x != line.end.x){
			k2 = (line.end.y - line.start.y) / (line.end.x - line.start.x);
			b2 = line.start.y - k2 * line.start.x;
		}else{
			lim2 = true;
		}

		if(!lim1 && !lim2){
			if(k1 != k2){
				pt.x = (b2 - b1) / (k1 - k2);
				pt.y = k1 * pt.x + b1;
			}
		}else if(lim1 && !lim2){
			pt.x = b2;
			pt.y = k2 * pt.x + b2;
		}else if(!lim1 && lim2){
			pt.x = b1;	
			pt.y = k1 * pt.x + b1;
		}

		if(pt.x < 0 || pt.y < 0 || !onLine(pt) || !line.onLine(pt) ){
			pt.x = -1;
			pt.y = -1;
		}
		return pt;
	}
};

//计算最短路径 floyd算法
vector< vector<double> > shortestPath(vector< vector<double> > graph){
	vector< vector<double> > path = graph;
	for(int k = 0;k < graph.size();k++){
		for(int i = 0;i < graph.size();i++){
			for(int j = 0;j < graph.size();j++){
				if(path[i][j] > graph[i][k] + graph[k][j]){
					path[i][j] = graph[i][k] + graph[k][j];
				}
			}
		}
	}
	return path;
}

int main()
{
	int lineCount = 0;
	cin >> lineCount;
	vector<Line> lines;

	//读取各条线段
	for(int i = 0;i < lineCount;i++){
		Point start,end;
		cin >> start.x >> start.y >> end.x >> end.y;
		lines.push_back(Line(start,end));
	}

	vector<Point> points;

	//计算交点
	for(size_t sx = 0; sx < lines.size();sx++){
		for(size_t sy = sx;sy < lines.size();sy++){
			Point pt = lines[sx].calcPoint(lines[sy]);
			if(pt.x != -1 && pt.y != -1) points.push_back(pt);
		}
	}

	Point startPt,endPt,calPt;
	cin >> startPt.x >> startPt.y >> endPt.x >> endPt.y;

	//将起点放入集合
	points.push_back(startPt);
	double shortest = 15000;

	//计算离终点最近的那个点的位置
	for(size_t index = 0;index < lines.size();index++){
		Path path = lines[index].shortestDistance(endPt);
		if(path.distance < shortest){
			shortest = path.distance;
			calPt = path.pt;
		}
	}
	points.push_back(calPt);

	vector< vector<double> > matrix(points.size());
	
	size_t ip,jp;

	//下面两个循环用来 构造邻接矩阵
	for(ip = 0;ip < matrix.size();ip++){
		vector<double> to(points.size());
		for(jp = 0;jp < points.size();jp++){
			to[jp] = MAXDIS;
		}
		matrix[ip] = to;
	}

	for(ip = 0;ip < points.size();ip++){
		for(jp = ip;jp < points.size();jp++){
			bool onLine = false;
			vector<Line>::iterator lit = lines.begin();
			while(lit != lines.end()){
				if((ip != jp) && 
					(*lit).onLine(points[ip]) && (*lit).onLine(points[jp])){
					onLine = true;
					break;
				}
				lit++;
			}
			if(onLine){
				double dx = fabs(points[ip].x - points[jp].x);
				double dy = fabs(points[ip].y - points[jp].y);
				double distance = sqrt(dx * dx + dy * dy);
				matrix[jp][ip] = matrix[ip][jp] = distance;
			}
		}
	}


	vector< vector<double> > path = shortestPath(matrix);
	cout.precision(2);
	cout <<  path[points.size()-2][points.size()-1] << endl;
}