【说明】[程序6说明]单源最短路径的分支限界算法。
const int MAXNUM=29999；
#include＜iostream＞
#include＜vector＞
#include＜algorithm＞
#include＜functional＞
using namespace std；
template ＜class VertexType,class EdgeType＞
class MinNode //程序中使用的最小化堆的结点说明
friend class Graph＜VertexType,EdgeType＞
public:
MinNode (int nl, EdgeType length1)
VexNum=nl；
length=length1；bool operator＞(const MinNode＜VertexType,EdgeType＞&p)const
return (1) ＞p.length；private:
int VexNum;
//记录源点序号，序号数组p及distance下标相一致。源点为初始扩展顶点
EdgeType length;
//记录源点到本顶点的当前最短路径的长度，源点到自身的长度为0template＜class VertexType,classEdgeType＞
void Graph＜VertexType,EdgeType＞:: shortestpath(VertexType start)
int j,k,source;//source 记录源点的序号。
EdgeType*distance= (2) ；
int*p=new int[MaxNumVertex];
vector＜MinNode＜VertexType,EdgeType＞ ＞H；
for(source=0；source＜MaxNumVertex;source++)
if(NodeList[source]==start)break；
if (source＞=MaxNumVertex)cout＜＜”This is error!”＜＜end1；return；
MinNode＜VertexType,Edge Type＞ (3) ；
for(k=0；k＜MaxNumVertex；k++)
distance[k]：MAXXUM； //记录源点到本顶点k的最终的最短路径的长度
p[k]=source； //记录最短路径上的本顶点的直接前驱顶点的序号

distance[source]=0；p[source]=-1；//m 是源点，前一顶点不存在
vector＜MinNode＜VertexType, EdgeType＞＞::iterator q；
while(1)
for(j=0；j＜MaxNumVertex；j++)
if((AdjMatrix[E.VexNum* MaxNumVertex+j]＜MAXNUM)
&&( (4) ＜distance[j]))
distance[j]=E.length+AdjMatrix[E.VexNum* MaxNumVertex+j]；
p[j]=E. VexNum； //记录顶点j的前一顶点
MinNode＜VertexType, EdgeType＞ (5) ；
H．push_ back(N)；
push_heap(H. begin（　），H.end（　），greater＜MinNode＜VertexType，
EdgeType＞＞（　）)；

if(H.empty（　）＝true)break； //若优先队列为空，那么算法结束
else
pop_ heap(H.begin（　），H. end（　），greater＜MinNode＜VertexType，
EdgeType＞＞（　）)；
q=H.end（　）-1； //从最小化堆中取路径最短的顶点
E=*q；
H.pop_ back（　）； //删除从最小化堆中“挤”出的顶点

//end while
for(k=0；k＜MaxNumVertex；k++)
cout＜＜"Shorstest path from vertex"＜＜k＜＜"is"＜＜distance[k]＜＜end1；
j=k；cout＜＜"All vertices are："；
while(j!=source)cout＜＜j＜＜"-＞"；j=p[j]；
cout＜＜source＜＜”.”＜＜end1；
//打印顶点的最短路径长度和至源点的最短路径上经过的顶点序列
return；

【说明】[程序6说明]单源最短路径的分支限界算法。 const int MAXNUM=29999； #include＜iostream＞ #include＜vector＞ #include＜algorithm＞ #include＜functional＞ using namespace std； template ＜class VertexType,class EdgeType＞ class MinNode { //程序中使用的最小化堆的结点说明 friend class Graph＜VertexType,EdgeType＞ public: MinNode (int nl, EdgeType length1) { VexNum=nl； length=length1； } bool operator＞(const MinNode＜VertexType,EdgeType＞&p)const { return (1) ＞p.length； } private: int VexNum; //记录源点序号，序号数组p及distance下标相一致。源点为初始扩展顶点 EdgeType length; //记录源点到本顶点的当前最短路径的长度，源点到自身的长度为0 } template＜class VertexType,classEdgeType＞ void Graph＜VertexType,EdgeType＞:: shortestpath(VertexType start) { int j,k,source;//source 记录源点的序号。 EdgeType*distance= (2) ； int*p=new int[MaxNumVertex]; vector＜MinNode＜VertexType,EdgeType＞ ＞H； for(source=0；source＜MaxNumVertex;source++) { if(NodeList[source]==start)break；} if (source＞=MaxNumVertex){cout＜＜”This is error!”＜＜end1；return；} MinNode＜VertexType,Edge Type＞ (3) ； for(k=0；k＜MaxNumVertex；k++) { distance[k]：MAXXUM； //记录源点到本顶点k的最终的最短路径的长度 p[k]=source； //记录最短路径上的本顶点的直接前驱顶点的序号 } distance[source]=0；p[source]=-1；//m 是源点，前一顶点不存在 vector＜MinNode＜VertexType, EdgeType＞＞::iterator q； while(1){ for(j=0；j＜MaxNumVertex；j++) if((AdjMatrix[E.VexNum* MaxNumVertex+j]＜MAXNUM) &&( (4) ＜distance[j])) { distance[j]=E.length+AdjMatrix[E.VexNum* MaxNumVertex+j]； p[j]=E. VexNum； //记录顶点j的前一顶点 MinNode＜VertexType, EdgeType＞ (5) ； H．push_ back(N)； push_heap(H. begin（　），H.end（　），greater＜MinNode＜VertexType， EdgeType＞＞（　）)； } if(H.empty（　）＝true)break； //若优先队列为空，那么算法结束 else{ pop_ heap(H.begin（　），H. end（　），greater＜MinNode＜VertexType， EdgeType＞＞（　）)； q=H.end（　）-1； //从最小化堆中取路径最短的顶点 E=*q； H.pop_ back（　）； //删除从最小化堆中“挤”出的顶点 } } //end while for(k=0；k＜MaxNumVertex；k++){ cout＜＜"Shorstest path from vertex"＜＜k＜＜"is"＜＜distance[k]＜＜end1； j=k；cout＜＜"All vertices are："； while(j!=source){cout＜＜j＜＜"-＞"；j=p[j]；} cout＜＜source＜＜”.”＜＜end1； } //打印顶点的最短路径长度和至源点的最短路径上经过的顶点序列 return； }

请使用VC6或使用[答题]菜单打开考生文件夹proj2下的工程proj2，该工程中包含一个程序文件main.cpp，其中有坐标点类point、线段类Line和三角形类Triangle的定义，还有main函数的定义。程序中两点间距离的计算是按公式 实现的，三角形面积的计算是按公式 实现的，其中 。请在程序中的横线处填写适当的代码，然后删除横线，以实现上述类定义。此程序的正确输出结果应为： Side 1:9.43398 Side 2:5 Side 3:8 area:20 注意：只在横线处填写适当的代码，不要改动程序中的其他内容，也不要删除或移动“//****found****”。 #include＜iostream＞ #include＜cmath＞ using namespace std; class Point //坐标点类 public: const double x,y; Point(double x=0.0,double y=0.0):x(x),y(y) //**********found********** double distanceTo(______) const //到指定点的距离 return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y)); ; class line//线段类 public: const Point p1,p2;//线段的两个端点 //**********found********** Line(Point p1,Point p2):______ double length（　）const return p1.distanceTo(p2);//线段的长度 ； class Triangle//三角形类 public: const Point pl, p2,p3;//三角形的三个顶点 //**********found********** Triangle(______):p1(p1),p2(p2),p3(p3) double length1（　）const//边p1,p2的长度return Line(p1,p2).length（　）; double length2（　）const//边p2,p3的长度 return Line(p2,p3).length（　）; double length3（　）const//边p3,p1的长度 return Line(p3,p1).length（　）; double area（　） const//三角形面积 //**********found********** double S=______; return sqrt(s*(s-lengthl（　）)*(s-length2（　）)*(s-length3（　）)); ; int main （　） Triangle r(Point(0.0,8.0),Point(5.0,0.0),Point(0.0,0.0)); cout＜＜"Side 1:"＜＜r.length1（　）＜＜endl; cout＜＜"Side 2:"＜＜r.length2（　）＜＜endl; cout＜＜"Side 3:"＜＜r.length3（　）＜＜endl; cout＜＜"area:"＜＜r.area（　）＜＜endl; return 0;

(A)const Point&p
(B)pA(pA),pB(pB)
(C)Point pA,Point pB,Point pC
(D)(lengthA()+lengthB()+lengthC())/B