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

野性酷女 2022-12-22 09:47 170阅读 0赞

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

### [紧急救援][Link 1] ###

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]  
该题与 [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，也能设定为其他数值。

[Link 1]: https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/cec17f5ce1a3446a9c328b04cef51b65.png
[Dijkstra]: https://blog.csdn.net/Zhengyangxinn/article/details/109568092