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

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<iostream>#include<cmath>#include<cstdio>#include<vector>#include<algorithm>#include<cstring>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<n;i++)    {           int t=-1;        for(int j=0;j<n;j++)            if(!st[j] && (t==-1 || dis[j]<dis[t]))                t=j;                st[t]=true;                for(int j=0;j<n;j++) dis[j]=min(dis[j],dis[t]+g[t][j]);    }        return dis[D];}void dfs(int u,int f,int sum,int distance){       if(distance>dis[D]) return ;        if(u==D)    {           cnt++;        if(sum>ans)            for(int i=0;i<idx;i++)             {                   res[i]=path[i];                tot = idx;                ans=sum;            }                return ;    }        for(int i=0;i<n;i++)    {           if(g[u][i]!=inf && u!=i && !st[i])        {               if(i==f) continue;            st[i]=true;            path[idx++]=i;            dfs(i,u,sum+w[i],distance+g[u][i]);            st[i]=false;            idx--;        }    }}int main(){       scanf("%d%d%d%d",&n,&m,&S,&D);    for(int i=0;i<n;i++) scanf("%d",&w[i]);        memset(g,0x3f,sizeof g);    for(int i=0;i<m;i++)    {           int a,b,c;        scanf("%d%d%d",&a,&b,&c);        g[a][b]=g[b][a]=min(g[a][b],c);    }        dijkstra();        memset(st,false,sizeof st);    path[idx]=S;    res[idx++]=S;    dfs(S,-1,w[S],0);        printf("%d %d\n",cnt,ans);        for(int i=0;i<tot;i++)         printf("%d%c",res[i],i==tot-1? '\n' : ' ');        return 0;}