天梯题集——紧急救援（Dijkstra+倒序打印分析）

Dijkstra算法：用于求单源到其他点的最短路径。

紧急救援

该题与 Dijkstra模板题 的不同之处在于该题需要记录更多信息，主要思路从局部最优到整体最优，类似dp的思想。

#include<bits/stdc++.h>
#define maxv 510
#define INF 0x3f3f3f3f
#define ll long long 
using namespace std;

int mp[maxv][maxv];  // 地图
int w[maxv];         // 救援队数量

int dis[maxv];       // dijkstra各点到源点的最近距离
int cnt[maxv];       // 源点到各点最近距离相同的路径条数
int sum[maxv];      // 从源点走到各点可召集的消防员的最大值

int pre[maxv];       // 记录最短路径下城市的上一个城市 
bool flag[maxv];     // 访问标志
 
int M,N,S,D;

//打印 
void path(int k) {
    if(k<0) return;
    path(pre[k]);
    cout<<k;
    if(k!=D) cout<<" "; 
}
 
void dijkstra(int s) {
    fill(dis, dis+M, INF);		//对dis数组进行赋值 
    fill(flag, flag+M, false);
    fill(pre, pre+M, -1);
 
    //初始情况，起点到起点
    dis[s] = 0;
    sum[s]= w[s];
    cnt[s] = 1;
 	
 	//从局部最优到整体最优 
    while(1) {
        int v, Max=INF;
        
        //在所有未被访问的点中找一个距离最近的点作为当前最短路的终点
        for(int u=0; u<M; u++) 
        if(!flag[u] && Max>dis[u]){
			Max = dis[u];
           	v = u;
        }
 
        //如果所有点都起码已经访问过就终止循环
        if(Max==dis[u]) break;

        flag[v] = true;
        //更新路径
        for(int u=0; u<M; u++) {
            if(mp[v][u] == INF)
                continue;
			
			//存在更短路径 
            if(dis[v]+mp[v][u] < dis[u]){
                dis[u] = dis[v]+mp[v][u];
                pre[u] = v;			    //u的上一个城市v
 
                cnt[u] = cnt[v];		//u城市的最短路径数等于v城市的最短路径数 
                sum[u] = sum[v]+w[u];   //u城市的最大消防人数等于最短路径上的消防人员和 
            }
            //最短路径长度相等 
            else if(dis[v]+mp[v][u] == dis[u]){
                cnt[u] += cnt[v];
                
                //从最短路径中维护最大消防人员数量和路径 
                if(sum[v]+w[u] > sum[u]){
                    sum[u] = sum[v]+w[u];
                    pre[u] = v;	
                }
            }
        }
    }
 
    cout<<cnt[D]<<" "<<sum[D]<<endl;
    path(D);	//倒序打印 
    cout<<endl;
    
    return; 
}
 
int main() {
    cin>>M>>N>>S>>D;
 
    for(int i=0; i<M; i++)
    for(int j=0; j<M; j++)
        mp[i][j] = INF;
    
    for(int i=0; i<M; i++)
        cin>>w[i];
 
    for(int i=0; i<N; i++) {
        int a,b;
        cin>>a>>b;
        cin>>mp[a][b];
        mp[b][a] = mp[a][b];
    }
    
    dijkstra(S);
 
    return 0;
}

其中我认为有一点值得思考，为什么要倒序打印？
假如正序存储再正序打印结果会是怎么样的？

//正序存储路径并打印
#include<bits/stdc++.h>
#define maxv 500+8
#define INF 0x3f3f3f3f
#define ll long long 
using namespace std;

int mp[maxv][maxv]; 
int w[maxv];       

int dis[maxv];      
int cnt[maxv];       
int sum[maxv];    

int next[maxv];      
bool flag[maxv]={false};   
 
int M,N,S,D;

//打印 
void path(int k) {
    cout<<k;
    if(k!=D)
		cout<<" ";
	if(k==D) return;
	path(next[k]);
}
 
void dijkstra(int s) {
    fill(dis, dis+M, INF);		
    fill(flag, flag+M, false);
    fill(next, next+M, -1);
 
    dis[s] = 0;
    sum[s]= w[s];
    cnt[s] = 1;
 
	//每个 v 只能改变一次，不能更新
	//不可正序记录路径。 
    while(1) {
        int v, Max=INF;
        
        for(int u=0; u<M; u++) 
        if(!flag[u] && dis[u]<Max){
			Max = dis[u];
           	v = u;
        }
 
        if(Max==INF) break;
        flag[v] = true;
        
        for(int u=0; u<M; u++) {
            if(mp[v][u] == INF||v==u)
                continue;
			
            if(dis[v]+mp[v][u] < dis[u]){
                dis[u] = dis[v]+mp[v][u];
                next[v] = u;			 
 
                cnt[u] = cnt[v];		
                sum[u] = sum[v]+w[u];   
            }
            else if(dis[v]+mp[v][u] == dis[u]){
                cnt[u] += cnt[v];
               
                if(sum[v]+w[u] > sum[u]){
                    sum[u] = sum[v]+w[u];
                    next[v] = u;	
                }
            }
        }
    }
    cout<<cnt[D]<<" "<<sum[D]<<endl;
    path(S);
    cout<<endl;
    
    return; 
}
 
int main() {
    cin>>M>>N>>S>>D;
 
    for(int i=0; i<M; i++)
    for(int j=0; j<M; j++)
        mp[i][j] = INF;
    
    for(int i=0; i<M; i++)
        cin>>w[i];
 
    for(int i=0; i<N; i++) {
        int a,b;
        cin>>a>>b;
        cin>>mp[a][b];
        mp[b][a] = mp[a][b];
    }
    
    dijkstra(S);
 
    return 0;
}

将样例一放在正序打印代码上，结果是错误的。
正序打印：每次确定最佳方案下 v 城市下一个城市。
倒序打印：每次预测最佳方案下哪些城市的下一个城市是 v 城市。

我们不能够在未知其他城市与 D 的距离下，确定 S 城市的下一个城市。
但我们能够通过查找最优方案下提前预测哪些城市的下一个城市是 S。
似乎有点玄，但是很妙…

补充 fill() 函数

//将arr数组中的元素都赋值为 2
#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int arr[10];
    fill(arr, arr + 10, 2);
    return 0;
}

fill() 函数类似于 memset() 函数，但会更加便利。
memset() 函数常用来对数组进行置 0 。
fill() 函数不单可以对数组进行置 0，也能设定为其他数值。