二、搜索与图论6：Dijkstra 模板题+算法模板（Dijkstra求最短路 I, Dijkstra求最短路 II，1003 Emergency）

妖狐艹你老母 2023-10-14 13:09 20阅读 0赞

#### 文章目录 ####

*  算法模板
 *   *  Dijkstra题目代码模板
     *   *  朴素dijkstra算法
         *  堆优化版dijkstra
     *  树与图的存储
     *   *  (1) 邻接矩阵：
         *  (2) 邻接表：
         *  关于e\[\],ne\[\],h\[\]的理解
     *  关于堆的原理与操作
 *  模板题
 *   *  Dijkstra求最短路 I
     *   *  原题链接
         *  题目
         *  思路
         *  题解
     *  Dijkstra求最短路 II
     *   *  原题链接
         *  题目
         *  思路
         *  题解
     *  1003 Emergency
     *   *  原题链接
         *  题目
         *  思路
         *  题解

## 算法模板 ##

![在这里插入图片描述][f856acc61548455898c776c8c1130fa4.png]

### Dijkstra题目代码模板 ###

#### 朴素dijkstra算法 ####

对应模板题：Dijkstra求最短路 I  
时间复杂是 O(n^2+m)：n 表示点数，m 表示边数  
![在这里插入图片描述][4fe84b83a3e6414ca17e82828f8b1012.png]  
![在这里插入图片描述][e144dd6a301a49a4933f61f400664e19.png]  
![在这里插入图片描述][0560ba5614bf4fd3a960112a30335543.png]

int g[N][N];  // 存储每条边
    int dist[N];  // 存储1号点到每个点的最短距离
    bool st[N];   // 存储每个点的最短路是否已经确定
    
    // 求1号点到n号点的最短路，如果不存在则返回-1
    int dijkstra()
    {
        
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
    
        for (int i = 0; i < n - 1; i ++ )
        {
        
            int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
            for (int j = 1; j <= n; j ++ )
                if (!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;
    
            // 用t更新其他点的距离
            for (int j = 1; j <= n; j ++ )
                dist[j] = min(dist[j], dist[t] + g[t][j]);
    
            st[t] = true;
        }
    
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

#### 堆优化版dijkstra ####

对应模板题：Dijkstra求最短路 II  
时间复杂度 O(mlogn)：n 表示点数，m 表示边数  
![在这里插入图片描述][99ece51bbc0b43b292a8c4340b4f5161.png]  
![在这里插入图片描述][5d0f5d6bd5dd4bd98c94799da107ee25.png]  
![在这里插入图片描述][e941afaf47ce4409a9c76cd49a60e556.png]

typedef pair<int, int> PII;
    
    int n;      // 点的数量
    int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
    int dist[N];        // 存储所有点到1号点的距离
    bool st[N];     // 存储每个点的最短距离是否已确定
    
    // 求1号点到n号点的最短距离，如果不存在，则返回-1
    int dijkstra()
    {
        
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        heap.push({
        0, 1});      // first存储距离，second存储节点编号
    
        while (heap.size())
        {
        
            auto t = heap.top();
            heap.pop();
    
            int ver = t.second, distance = t.first;
    
            if (st[ver]) continue;
            st[ver] = true;
    
            for (int i = h[ver]; i != -1; i = ne[i])
            {
        
                int j = e[i];
                if (dist[j] > distance + w[i])
                {
        
                    dist[j] = distance + w[i];
                    heap.push({
        dist[j], j});
                }
            }
        }
    
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

### 树与图的存储 ###

**树是一种特殊的图**，与图的存储方式相同。  
对于无向图中的边ab，存储两条有向边a->b, b->a。  
因此我们可以只考虑有向图的存储。

#### (1) 邻接矩阵： ####

g\[a\]\[b\] 存储边a->b

#### (2) 邻接表： ####

[https://www.acwing.com/video/21/][https_www.acwing.com_video_21]  
（1:20:00左右）

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
    int h[N], e[N], ne[N], idx;
    
    // 添加一条边a->b
    void add(int a, int b)
    {
        
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    int main(){
        
    	...
    	// 初始化
    	idx = 0;
    	memset(h, -1, sizeof h);
    	...
    }

有权重时模板：

int h[N],w[N],e[N],ne[N],idx; 
    
    void add(int a,int b,int c){
        
    	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    }

#### 关于e\[\],ne\[\],h\[\]的理解 ####

![在这里插入图片描述][a5f339f399424762a06fdd6547e79e5e.jpeg]  
**h\[N\]** : 表示 第 i 个节点的 第一条边的 idx  
**ne\[M\]** : 表示 与 第 idx 条边 同起点 的 下一条边 的 idx  
**e\[M\]** : 表示 第idx 条边的 终点

**N** ： 节点数量  
**M**：边的数量  
**i** : 节点的下标索引  
**idx** ： 边的下标索引  
变量初始化定义：

int h[N], e[M], ne[M], idx;

当我们加入一条边的时候：

void add(int a,int b){
        
         e[idx] = b;      // 记录 加入的边 的终点节点
         ne[idx] = h[a]; // h[a] 表示 节点 a 为起点的第一条边的下标，ne[idx] = h[a] 表示把 h[a] 这条边接在了 idx 这条边的后面，其实也就是把 a 节点的整条链表 接在了 idx 这条边 后面；目的就是为了下一步 把 idx 这条边 当成 a 节点的单链表的 第一条边，完成把最新的一条边插入到 链表头的操作；
         h[a] = idx++; // a节点开头的第一条边置为当前边，idx移动到下一条边
    }

要注意的是邻接表插入新节点时使用的是“头插”，如图中节点2：当插入2 1时此时为2—>1, 而后插入2 4后，此时为 2—> 4 —> 1.  
![在这里插入图片描述][85f4b04d48fc43cd98b66ba7c7593f0a.png]

### 关于堆的原理与操作 ###

[二、数据结构10：堆 模板题+算法模板（堆排序，模拟堆）][10_]

## 模板题 ##

### Dijkstra求最短路 I ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/851/][https_www.acwing.com_problem_content_851]

#### 题目 ####

给定一个 n  
个点 m  
条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1  
号点到 n  
号点的最短距离，如果无法从 1  
号点走到 n  
号点，则输出 −1  
。

输入格式  
第一行包含整数 n  
和 m  
。

接下来 m  
行每行包含三个整数 x,y,z  
，表示存在一条从点 x  
到点 y  
的有向边，边长为 z  
。

输出格式  
输出一个整数，表示 1  
号点到 n  
号点的最短距离。

如果路径不存在，则输出 −1  
。

数据范围  
1≤n≤500  
,  
1≤m≤105  
,  
图中涉及边长均不超过10000。

输入样例：

3 3
    1 2 2
    2 3 1
    1 3 4

输出样例：

#### 思路 ####

![在这里插入图片描述][4ef336361b2f4acba35235050a8b44b2.png]  
![在这里插入图片描述][969ade3940d5466382aeb51b099319f0.png]

#### 题解 ####

#include <iostream>
    #include <algorithm>
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 510;
    const int M = 1e5 + 10;
    int dist[N]; // 存各点与1号点的最短距离 
    bool st[N]; // 存各点是否已被 处理为最短距离点 判断 (当前已确定最短距离的点) 
    int g[N][N];
    int n,m,t;
    
    int dijkstra(){
        
    
    	memset(dist,0x3f,sizeof dist);
    	dist[1] = 0;
    	for(int i = 0;i<n;i++){
        
    		t = -1; //	t: 不在 当前已确定最短距离的点 中的距离最短的点 初始化为-1 
    		for(int j = 1;j<=n;j++){
        
    			if(!st[j] && (t == -1 || dist[t] > dist[j])){
        
    				t = j;
    			}
    		}
    		
    		st[t] = true;
    		for(int j=1;j<=n;j++){
        
    			dist[j] = min(dist[j],dist[t] + g[t][j]); //用（1到t+t到j）的长度与（1到j）的长度进行对比更新 
    		}
    		
    	}
    	if(dist[n] == 0x3f3f3f3f) return -1;
    	else return dist[n];
    }
    int main(){
        
    	cin>>n>>m;
    	memset(g,0x3f,sizeof g);
    	for(int i=0;i<m;i++){
        
    		int x,y,z;
    		cin>>x>>y>>z;
    		g[x][y] = min(g[x][y],z);
    		
    	}	
    	
    	int res = dijkstra();
    	
    	printf("%d",res);
    	
    	return 0;
    	
    	
    }

### Dijkstra求最短路 II ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/852/][https_www.acwing.com_problem_content_852]

#### 题目 ####

给定一个 n  
个点 m  
条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1  
号点到 n  
号点的最短距离，如果无法从 1  
号点走到 n  
号点，则输出 −1  
。

输入格式  
第一行包含整数 n  
和 m  
。

接下来 m  
行每行包含三个整数 x,y,z  
，表示存在一条从点 x  
到点 y  
的有向边，边长为 z  
。

输出格式  
输出一个整数，表示 1  
号点到 n  
号点的最短距离。

如果路径不存在，则输出 −1  
。

数据范围  
1≤n,m≤1.5×105  
,  
图中涉及边长均不小于 0  
，且不超过 10000  
。  
数据保证：如果最短路存在，则最短路的长度不超过 109  
。

输入样例：

3 3
    1 2 2
    2 3 1
    1 3 4

输出样例：

#### 思路 ####

使用堆优化，选择用stl中的priority\_queue进行操作  
![在这里插入图片描述][fdba1f9319af40cd9216a17e04c53a4a.png]  
关于st\[N\]数组 处理冗余部分  
[https://www.acwing.com/solution/content/167860/][https_www.acwing.com_solution_content_167860]

#### 题解 ####

#include <iostream>
    #include <algorithm>
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 2e5 + 10;
    const int M = 2e5 + 10;
    typedef pair<int,int> PII;
    int dist[N]; // 存各点与1号点的最短距离 
    bool st[N]; // 存各点是否已被 处理为最短距离点 判断 (当前已确定最短距离的点) 
    //int g[N][N];
    //堆优化中，由于为稀疏图，因此使用邻接表进行存储
    int h[N],w[N],e[N],ne[N],idx; 
    
    int n,m,t;
    
    //邻接表插入处理 
    void add(int a,int b,int c){
        
    	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    }
    
    int dijkstra(){
        
    
    	memset(dist,0x3f,sizeof dist);
    	dist[1] = 0;
    	
    //	堆优化版dijkstra
    	priority_queue<PII,vector<PII>,greater<PII>> heap;
    	heap.push({
        0,1}); // {距离，编号}编号为1的点距离为0，表示1到1的距离为0 
    	
    	while(heap.size()){
        
    		auto t = heap.top();
    		heap.pop();
    		
    		int ver = t.second, distance = t.first; // distance :结点1到结点ver的距离
    		if(st[ver]) continue;  // 冗余的话跳过
    		st[ver] = true;
    		
    		for(int i=h[ver]; i!=-1; i=ne[i]){
         // 邻接表遍历,从h[ver]开始遍历可达的所有结点
    			int j = e[i];
    			
    //			w[i]:结点ver到结点j的距离
    			if(dist[j]>distance + w[i]){
         // 1--->i的距离 和 1--->ver--->i的距离相比
    				dist[j] = distance + w[i]; 
    				heap.push({
        dist[j],j});
    			}
    		} 
    	}
    	
    	if(dist[n] == 0x3f3f3f3f) return -1;
    	else return dist[n];
    }
    int main(){
        
    	cin>>n>>m;
    //	memset(g,0x3f,sizeof g);
    	memset(h,-1,sizeof h);;
    	for(int i=0;i<m;i++){
        
    		int x,y,z;
    		cin>>x>>y>>z;
    		add(x,y,z);
    		
    	}	
    	
    	int res = dijkstra();
    	
    	printf("%d",res);
    	
    	return 0;
    	
    	
    }

### 1003 Emergency ###

#### 原题链接 ####

[原题链接][Link 1]

#### 题目 ####

题目大意：n个城市m条路，每个城市有救援小组，所有的边的边权已知。给定起点和终点，求从起点到终点的最短路径条数以及最短路径上的救援小组数目之和。如果有多条就输出点权（城市救援小组数目）最大的那个

#### 思路 ####

用一遍Dijkstra算法，救援小组个数相当于点权，用Dijkstra求边权最小的最短路径的条数，以及这些最短路径中点权最大的值  
dis\[i\]表示从出发点到i结点最短路径的路径长度，  
num\[i\]表示从出发点到i结点最短路径的条数，  
w\[i\]表示从出发点到i点救援队的数目之和  
当判定dis\[u\] + e\[u\]\[v\] < dis\[v\]的时候，  
不仅仅要更新dis\[v\]，还要更新num\[v\] = num\[u\], w\[v\] = weight\[v\] + w\[u\];  
如果dis\[u\] + e\[u\]\[v\] == dis\[v\]，还要更新num\[v\] += num\[u\]，而且判断一下是否权重w\[v\]更小，如果更小了就更新w\[v\] = weight\[v\] + w\[u\];

#### 题解 ####

基于上述朴素版dijkstra进行改进，

#include <bits/stdc++.h>
    using namespace std;
    //题目大意：n个城市m条路，每个城市有救援小组，所有的边的边权已知。给定起点和终点，求从起点到终点的最短路径条数以及最短路径上的救援小组数目之和。如果有多条就输出点权（城市救援小组数目）最大的那个～
    //
    //分析：用一遍Dijkstra算法～救援小组个数相当于点权，用Dijkstra求边权最小的最短路径的条数，以及这些最短路径中点权最大的值～dis[i]表示从出发点到i结点最短路径的路径长度，num[i]表示从出发点到i结点最短路径的条数，w[i]表示从出发点到i点救援队的数目之和～当判定dis[u] + e[u][v] < dis[v]的时候，不仅仅要更新dis[v]，还要更新num[v] = num[u], w[v] = weight[v] + w[u]; 如果dis[u] + e[u][v] == dis[v]，还要更新num[v] += num[u]，而且判断一下是否权重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u]; 
    
    const int N = 510;
    int g[N][N];
    int c1,c2;
    int dist[N]; //dist[i]表示从出发点到i结点最短路径的路径长度
    int weight[N]; //每个城市救援队数量
    int w[N]; //w[i]表示从出发点到i点救援队的数目之和
    bool st[N]; 
    int num[N]; //num[i]表示从出发点到i结点最短路径的条数
    
    int n,m;
    
    void dij(){
        
    	w[c1] = weight[c1];
    	memset(dist,0x3f,sizeof dist);
    	dist[c1] = 0;
    	num[c1] = 1;
    	int t;
    	for(int i=0;i<n;i++){
        
    		t = -1;
    		for(int j=0;j<n;j++){
        
    			if(!st[j] && (t==-1 || dist[t] >dist[j]) )
    			{
        
    				t = j;
    			}
    		}
    		st[t] = true;
    		for(int j=0;j<n;j++){
        
    //			dist[j] = min(dist[j],dist[t] + g[t][j]);
    			if(dist[j]>dist[t]+g[t][j]){
         //当判定dis[u] + e[u][v] < dis[v]的时候，不仅仅要更新dis[v]，还要更新num[v] = num[u], w[v] = weight[v] + w[u]; 
    				dist[j] = dist[t]+g[t][j];
    				num[j] = num[t];
    				w[j] = w[t] + weight[j];  
    //				cout<<t<<" "<<w[t]<<endl;
    //				w[j]+=weight[t];
    			}
    			else if(dist[j]==dist[t]+g[t][j]){
         //如果dis[u] + e[u][v] == dis[v]，还要更新num[v] += num[u]，而且判断一下是否权重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u]; 
    				num[j] = num[t]+num[j];
    				if(w[t]+weight[j] > w[j]){
        
    					w[j] = w[t] + weight[j];
    				}
    			}	
    		}
    	}
    	
    //	return w[c2];	
    }
    int main(){
        
    	cin>>n>>m>>c1>>c2;
    	
    	for(int i=0;i<n;i++){
        
    		int t;
    		cin>>t;
    		weight[i] = t;
    	}
    	memset(g,0x3f,sizeof g); // 赋值无穷大 
    	
    	for(int i=0;i<m;i++){
        
    		int x,y,z;
    		cin>>x>>y>>z;
    		g[x][y] = g[y][x] = z; // 无向图！所以存双向信息 
    	}
    	
    	dij();
    	
    	cout<<num[c2]<<" "<<w[c2];
    }

参考链接：[1003. Emergency (25)-PAT甲级真题（Dijkstra算法）][1003. Emergency _25_-PAT_Dijkstra]

[f856acc61548455898c776c8c1130fa4.png]: https://img-blog.csdnimg.cn/f856acc61548455898c776c8c1130fa4.png
[4fe84b83a3e6414ca17e82828f8b1012.png]: https://img-blog.csdnimg.cn/4fe84b83a3e6414ca17e82828f8b1012.png
[e144dd6a301a49a4933f61f400664e19.png]: https://img-blog.csdnimg.cn/e144dd6a301a49a4933f61f400664e19.png
[0560ba5614bf4fd3a960112a30335543.png]: https://img-blog.csdnimg.cn/0560ba5614bf4fd3a960112a30335543.png
[99ece51bbc0b43b292a8c4340b4f5161.png]: https://img-blog.csdnimg.cn/99ece51bbc0b43b292a8c4340b4f5161.png
[5d0f5d6bd5dd4bd98c94799da107ee25.png]: https://img-blog.csdnimg.cn/5d0f5d6bd5dd4bd98c94799da107ee25.png
[e941afaf47ce4409a9c76cd49a60e556.png]: https://img-blog.csdnimg.cn/e941afaf47ce4409a9c76cd49a60e556.png
[https_www.acwing.com_video_21]: https://www.acwing.com/video/21/
[a5f339f399424762a06fdd6547e79e5e.jpeg]: https://img-blog.csdnimg.cn/a5f339f399424762a06fdd6547e79e5e.jpeg
[85f4b04d48fc43cd98b66ba7c7593f0a.png]: https://img-blog.csdnimg.cn/85f4b04d48fc43cd98b66ba7c7593f0a.png
[10_]: https://blog.csdn.net/GCTTTTTT/article/details/132066701?spm=1001.2014.3001.5501
[https_www.acwing.com_problem_content_851]: https://www.acwing.com/problem/content/851/
[4ef336361b2f4acba35235050a8b44b2.png]: https://img-blog.csdnimg.cn/4ef336361b2f4acba35235050a8b44b2.png
[969ade3940d5466382aeb51b099319f0.png]: https://img-blog.csdnimg.cn/969ade3940d5466382aeb51b099319f0.png
[https_www.acwing.com_problem_content_852]: https://www.acwing.com/problem/content/852/
[fdba1f9319af40cd9216a17e04c53a4a.png]: https://img-blog.csdnimg.cn/fdba1f9319af40cd9216a17e04c53a4a.png
[https_www.acwing.com_solution_content_167860]: https://www.acwing.com/solution/content/167860/
[Link 1]: https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805523835109376?type=7&page=0
[1003. Emergency _25_-PAT_Dijkstra]: https://blog.csdn.net/liuchuo/article/details/52300668