程序功能设计思路及结构说明：#includecstdio#includestring#includeiostream#includevectorusing namespace std;int NMSD;int p505; 点权 const int maxv = 1005;const int INF = 0x3fffffff;int Gmaxvmaxv; 邻接矩阵图 int dmaxv; 最短路径

程序功能：该程序用于求解给定图中从起点S到终点D的最短路径数量和路径上的最大点权和。

设计思路及结构说明：

1. 首先，定义了一些全局变量和常量：

   • N：表示图中的顶点数；
   • M：表示图中的边数；
   • S：表示起点；
   • D：表示终点；
   • p：数组，表示每个顶点的点权；
   • maxv：常量，表示图中顶点的最大数量；
   • INF：常量，表示无穷大；
   • G：邻接矩阵，表示图的连接关系；
   • d：数组，表示起点到每个顶点的最短路径长度；
   • vis：数组，表示顶点是否已被访问过；
   • pre：数组，逆序保存每个顶点的前驱节点；
   • tmpPath：临时路径，用于DFS遍历时保存当前路径；
   • path：最终路径，保存最短路径；
   • optValue：最大点权和；
   • num：最短路径数量。

2. 接下来，实现了Dijkstra算法来求解最短路径：

   • 初始化起点到其他顶点的最短路径长度为INF，起点到自身的最短路径长度为0；
   • 循环N次，每次选择一个未访问过的顶点u，将其标记为已访问；
   • 遍历所有未访问的顶点v，如果起点经过顶点u到达顶点v的路径长度小于当前记录的最短路径长度，则更新最短路径长度和前驱节点，并将顶点u加入前驱节点数组；
   • 如果起点经过顶点u到达顶点v的路径长度等于当前记录的最短路径长度，则将顶点u加入前驱节点数组。

3. 实现了DFS算法来遍历所有最短路径，并求解最大点权和：

   • 递归边界条件为当前顶点v等于起点S，此时找到一条完整的最短路径，将路径上的点权和计算出来并与当前最大点权和进行比较；
   • 递归式为将当前顶点v加入临时路径中，并遍历v的前驱节点，递归调用DFS函数；
   • 递归结束后，将当前顶点v从临时路径中移除。

4. 主函数部分：

   • 输入N、M、S、D以及每个顶点的点权；
   • 初始化邻接矩阵G，并读入每条边的起点、终点和权重；
   • 调用Dijkstra算法求解最短路径；
   • 调用DFS算法遍历所有最短路径，并求解最大点权和；
   • 输出最短路径数量和最大点权和；
   • 输出最短路径上的顶点序列。

该程序使用了Dijkstra算法和DFS算法来求解最短路径数量和路径上的最大点权和。其中，Dijkstra算法用于求解最短路径，DFS算法用于遍历所有最短路径并计算最大点权和