本文共 1642 字，大约阅读时间需要 5 分钟。

DIJ(最短路条数和具体方案) - 紧急救援 - 天梯赛 L2-001

题意：

$给定一个n个点(0到n-1)的无向图，要求从起点S到终点D的最短路径的条数，$

$同时，每个点都有一个点权，要求所有最短路中，点权最大的一条路径，$

$输出这个最大点权，以及这条路径。$

输入：

$首行包括四个正整数n,m,S,D，分别为点的数量，边的数量，起点编号和终点编号。$

$第二行包括n个正整数，表示每个点的点权。$

$接着m行表示m条边。$

输出：

$首行包括两个正整数，分别表示最短路的数量和最大点权和。$

$第二行输出这条路径。$

输入样例:

4 5 0 320 30 40 100 1 11 3 20 3 30 2 22 3 2

输出样例:

2 600 1 3

数据范围：

$2\le n\le 500$

时间限制： 200 ms

分析：

$根据点的数量，采用朴素版dijkstra算法，能够快速得出最短路的长度。$

$接着我们dfs所有最短路，用全局变量更新最短路条数和点权最大值。$

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 510, inf = 0x3f3f3f3f;int g[N][N];int n, m, dis[N];bool st[N];int w[N];int S,D;int cnt, ans;int path[N], res[N], idx, tot;int dijkstra(){ memset(dis,0x3f,sizeof dis); dis[S]=0; for(int i=0;i
         
          dis[D]) return ; if(u==D) { cnt++; if(sum>ans) for(int i=0;i