C++实现求解图中起点到终点的最短路径数量和最大点权和

"程序功能：该程序用于求解给定图中从起点S到终点D的最短路径数量和路径上的最大点权和。\n\n设计思路及结构说明：\n1. 首先，定义了一些全局变量和常量：\n - N：表示图中的顶点数；\n - M：表示图中的边数；\n - S：表示起点；\n - D：表示终点；\n - p：数组，表示每个顶点的点权；\n - maxv：常量，表示图中顶点的最大数量；\n - INF：常量，表示无穷大；\n - G：邻接矩阵，表示图的连接关系；\n - d：数组，表示起点到每个顶点的最短路径长度；\n - vis：数组，表示顶点是否已被访问过；\n - pre：数组，逆序保存每个顶点的前驱节点；\n - tmpPath：临时路径，用于DFS遍历时保存当前路径；\n - path：最终路径，保存最短路径；\n - optValue：最大点权和；\n - num：最短路径数量。\n\n2. 接下来，实现了Dijkstra算法来求解最短路径：\n - 初始化起点到其他顶点的最短路径长度为INF，起点到自身的最短路径长度为0；\n - 循环N次，每次选择一个未访问过的顶点u，将其标记为已访问；\n - 遍历所有未访问的顶点v，如果起点经过顶点u到达顶点v的路径长度小于当前记录的最短路径长度，则更新最短路径长度和前驱节点，并将顶点u加入前驱节点数组；\n - 如果起点经过顶点u到达顶点v的路径长度等于当前记录的最短路径长度，则将顶点u加入前驱节点数组。\n\n3. 实现了DFS算法来遍历所有最短路径，并求解最大点权和：\n - 递归边界条件为当前顶点v等于起点S，此时找到一条完整的最短路径，将路径上的点权和计算出来并与当前最大点权和进行比较；\n - 递归式为将当前顶点v加入临时路径中，并遍历v的前驱节点，递归调用DFS函数；\n - 递归结束后，将当前顶点v从临时路径中移除。\n\n4. 主函数部分：\n - 输入N、M、S、D以及每个顶点的点权；\n - 初始化邻接矩阵G，并读入每条边的起点、终点和权重；\n - 调用Dijkstra算法求解最短路径；\n - 调用DFS算法遍历所有最短路径，并求解最大点权和；\n - 输出最短路径数量和最大点权和；\n - 输出最短路径上的顶点序列。\n\n该程序使用了Dijkstra算法和DFS算法来求解最短路径数量和路径上的最大点权和。其中，Dijkstra算法用于求解最短路径，DFS算法用于遍历所有最短路径并计算最大点权和。"