算法模板
Dijkstra題目代碼模板
樸素dijkstra算法
對(duì)應(yīng)模板題：Dijkstra求最短路 I
時(shí)間復(fù)雜是 O(n^2+m)：n 表示點(diǎn)數(shù)，m 表示邊數(shù)
int g[N][N]; // 存儲(chǔ)每條邊
int dist[N]; // 存儲(chǔ)1號(hào)點(diǎn)到每個(gè)點(diǎn)的最短距離
bool st[N]; // 存儲(chǔ)每個(gè)點(diǎn)的最短路是否已經(jīng)確定
// 求1號(hào)點(diǎn)到n號(hào)點(diǎn)的最短路，如果不存在則返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在還未確定最短路的點(diǎn)中，尋找距離最小的點(diǎn)
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他點(diǎn)的距離
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];
}
堆優(yōu)化版dijkstra
對(duì)應(yīng)模板題：Dijkstra求最短路 II
時(shí)間復(fù)雜度 O(mlogn)：n 表示點(diǎn)數(shù)，m 表示邊數(shù)
typedef pair<int, int> PII;
int n; // 點(diǎn)的數(shù)量
int h[N], w[N], e[N], ne[N], idx; // 鄰接表存儲(chǔ)所有邊
int dist[N]; // 存儲(chǔ)所有點(diǎn)到1號(hào)點(diǎn)的距離
bool st[N]; // 存儲(chǔ)每個(gè)點(diǎn)的最短距離是否已確定
// 求1號(hào)點(diǎn)到n號(hào)點(diǎ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存儲(chǔ)距離，second存儲(chǔ)節(jié)點(diǎn)編號(hào)
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];
}
樹(shù)與圖的存儲(chǔ)
樹(shù)是一種特殊的圖，與圖的存儲(chǔ)方式相同。
對(duì)于無(wú)向圖中的邊ab，存儲(chǔ)兩條有向邊a->b, b->a。
因此我們可以只考慮有向圖的存儲(chǔ)。
(1) 鄰接矩陣：
g[a][b] 存儲(chǔ)邊a->b
(2) 鄰接表：
https://www.acwing.com/video/21/
（1:20:00左右）
// 對(duì)于每個(gè)點(diǎn)k，開(kāi)一個(gè)單鏈表，存儲(chǔ)k所有可以走到的點(diǎn)。h[k]存儲(chǔ)這個(gè)單鏈表的頭結(jié)點(diǎn)
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);
...
}
有權(quán)重時(shí)模板：
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 ++;
}
關(guān)于e[],ne[],h[]的理解
h[N] : 表示 第 i 個(gè)節(jié)點(diǎn)的 第一條邊的 idx
ne[M] : 表示 與 第 idx 條邊 同起點(diǎn) 的 下一條邊 的 idx
e[M] : 表示 第idx 條邊的 終點(diǎn)
N ： 節(jié)點(diǎn)數(shù)量
M：邊的數(shù)量
i : 節(jié)點(diǎn)的下標(biāo)索引
idx ： 邊的下標(biāo)索引
變量初始化定義：
int h[N], e[M], ne[M], idx;
當(dāng)我們加入一條邊的時(shí)候：
void add(int a,int b){
e[idx] = b; // 記錄 加入的邊 的終點(diǎn)節(jié)點(diǎn)
ne[idx] = h[a]; // h[a] 表示 節(jié)點(diǎn) a 為起點(diǎn)的第一條邊的下標(biāo)，ne[idx] = h[a] 表示把 h[a] 這條邊接在了 idx 這條邊的后面，其實(shí)也就是把 a 節(jié)點(diǎn)的整條鏈表 接在了 idx 這條邊 后面；目的就是為了下一步 把 idx 這條邊 當(dāng)成 a 節(jié)點(diǎn)的單鏈表的 第一條邊，完成把最新的一條邊插入到 鏈表頭的操作；
h[a] = idx++; // a節(jié)點(diǎn)開(kāi)頭的第一條邊置為當(dāng)前邊，idx移動(dòng)到下一條邊
}
要注意的是鄰接表插入新節(jié)點(diǎn)時(shí)使用的是“頭插”，如圖中節(jié)點(diǎn)2：當(dāng)插入2 1時(shí)此時(shí)為2—>1, 而后插入2 4后，此時(shí)為 2—> 4 —> 1.
關(guān)于堆的原理與操作
二、數(shù)據(jù)結(jié)構(gòu)10：堆 模板題+算法模板（堆排序，模擬堆）
模板題
Dijkstra求最短路 I
原題鏈接
https://www.acwing.com/problem/content/851/
題目
給定一個(gè) n
個(gè)點(diǎn) m
條邊的有向圖，圖中可能存在重邊和自環(huán)，所有邊權(quán)均為正值。
請(qǐng)你求出 1
號(hào)點(diǎn)到 n
號(hào)點(diǎn)的最短距離，如果無(wú)法從 1
號(hào)點(diǎn)走到 n
號(hào)點(diǎn)，則輸出 ?1
。
輸入格式
第一行包含整數(shù) n
和 m
。
接下來(lái) m
行每行包含三個(gè)整數(shù) x,y,z
，表示存在一條從點(diǎn) x
到點(diǎn) y
的有向邊，邊長(zhǎng)為 z
。
輸出格式
輸出一個(gè)整數(shù)，表示 1
號(hào)點(diǎn)到 n
號(hào)點(diǎn)的最短距離。
如果路徑不存在，則輸出 ?1
。
數(shù)據(jù)范圍
1≤n≤500
,
1≤m≤105
,
圖中涉及邊長(zhǎng)均不超過(guò)10000。
輸入樣例：
3 3
1 2 2
2 3 1
1 3 4
輸出樣例：
3
思路
題解
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
const int M = 1e5 + 10;
int dist[N]; // 存各點(diǎn)與1號(hào)點(diǎn)的最短距離
bool st[N]; // 存各點(diǎn)是否已被 處理為最短距離點(diǎn) 判斷 (當(dāng)前已確定最短距離的點(diǎ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: 不在 當(dāng)前已確定最短距離的點(diǎn) 中的距離最短的點(diǎn) 初始化為-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(luò)）的長(zhǎng)度與（1到j(luò)）的長(zhǎng)度進(jìn)行對(duì)比更新
}
}
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/
題目
給定一個(gè) n
個(gè)點(diǎn) m
條邊的有向圖，圖中可能存在重邊和自環(huán)，所有邊權(quán)均為非負(fù)值。
請(qǐng)你求出 1
號(hào)點(diǎn)到 n
號(hào)點(diǎn)的最短距離，如果無(wú)法從 1
號(hào)點(diǎn)走到 n
號(hào)點(diǎn)，則輸出 ?1
。
輸入格式
第一行包含整數(shù) n
和 m
。
接下來(lái) m
行每行包含三個(gè)整數(shù) x,y,z
，表示存在一條從點(diǎn) x
到點(diǎn) y
的有向邊，邊長(zhǎng)為 z
。
輸出格式
輸出一個(gè)整數(shù)，表示 1
號(hào)點(diǎn)到 n
號(hào)點(diǎn)的最短距離。
如果路徑不存在，則輸出 ?1
。
數(shù)據(jù)范圍
1≤n,m≤1.5×105
,
圖中涉及邊長(zhǎng)均不小于 0
，且不超過(guò) 10000
。
數(shù)據(jù)保證：如果最短路存在，則最短路的長(zhǎng)度不超過(guò) 109
。
輸入樣例：
3 3
1 2 2
2 3 1
1 3 4
輸出樣例：
3
思路
使用堆優(yōu)化，選擇用stl中的priority_queue進(jìn)行操作
關(guān)于st[N]數(shù)組 處理冗余部分
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]; // 存各點(diǎn)與1號(hào)點(diǎn)的最短距離
bool st[N]; // 存各點(diǎn)是否已被 處理為最短距離點(diǎn) 判斷 (當(dāng)前已確定最短距離的點(diǎn))
//int g[N][N];
//堆優(yōu)化中，由于為稀疏圖，因此使用鄰接表進(jìn)行存儲(chǔ)
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;
// 堆優(yōu)化版dijkstra
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1}); // {距離，編號(hào)}編號(hào)為1的點(diǎn)距離為0，表示1到1的距離為0
while(heap.size()){
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first; // distance :結(jié)點(diǎn)1到結(jié)點(diǎn)ver的距離
if(st[ver]) continue; // 冗余的話跳過(guò)
st[ver] = true;
for(int i=h[ver]; i!=-1; i=ne[i]){ // 鄰接表遍歷,從h[ver]開(kāi)始遍歷可達(dá)的所有結(jié)點(diǎn)
int j = e[i];
// w[i]:結(jié)點(diǎn)ver到結(jié)點(diǎn)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
原題鏈接
原題鏈接
題目
題目大意：n個(gè)城市m條路，每個(gè)城市有救援小組，所有的邊的邊權(quán)已知。給定起點(diǎn)和終點(diǎn)，求從起點(diǎn)到終點(diǎn)的最短路徑條數(shù)以及最短路徑上的救援小組數(shù)目之和。如果有多條就輸出點(diǎn)權(quán)（城市救援小組數(shù)目）最大的那個(gè)
思路
用一遍Dijkstra算法，救援小組個(gè)數(shù)相當(dāng)于點(diǎn)權(quán)，用Dijkstra求邊權(quán)最小的最短路徑的條數(shù)，以及這些最短路徑中點(diǎn)權(quán)最大的值
dis[i]表示從出發(fā)點(diǎn)到i結(jié)點(diǎn)最短路徑的路徑長(zhǎng)度，
num[i]表示從出發(fā)點(diǎn)到i結(jié)點(diǎn)最短路徑的條數(shù)，
w[i]表示從出發(fā)點(diǎn)到i點(diǎn)救援隊(duì)的數(shù)目之和
當(dāng)判定dis[u] + e[u][v] < dis[v]的時(shí)候，
不僅僅要更新dis[v]，還要更新num[v] = num[u], w[v] = weight[v] + w[u];
如果dis[u] + e[u][v] == dis[v]，還要更新num[v] += num[u]，而且判斷一下是否權(quán)重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u];
題解
基于上述樸素版dijkstra進(jìn)行改進(jìn)，文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-624430.html
#include <bits/stdc++.h>
using namespace std;
//題目大意：n個(gè)城市m條路，每個(gè)城市有救援小組，所有的邊的邊權(quán)已知。給定起點(diǎn)和終點(diǎn)，求從起點(diǎn)到終點(diǎn)的最短路徑條數(shù)以及最短路徑上的救援小組數(shù)目之和。如果有多條就輸出點(diǎn)權(quán)（城市救援小組數(shù)目）最大的那個(gè)～
//
//分析：用一遍Dijkstra算法～救援小組個(gè)數(shù)相當(dāng)于點(diǎn)權(quán)，用Dijkstra求邊權(quán)最小的最短路徑的條數(shù)，以及這些最短路徑中點(diǎn)權(quán)最大的值～dis[i]表示從出發(fā)點(diǎn)到i結(jié)點(diǎn)最短路徑的路徑長(zhǎng)度，num[i]表示從出發(fā)點(diǎn)到i結(jié)點(diǎn)最短路徑的條數(shù)，w[i]表示從出發(fā)點(diǎn)到i點(diǎn)救援隊(duì)的數(shù)目之和～當(dāng)判定dis[u] + e[u][v] < dis[v]的時(shí)候，不僅僅要更新dis[v]，還要更新num[v] = num[u], w[v] = weight[v] + w[u]; 如果dis[u] + e[u][v] == dis[v]，還要更新num[v] += num[u]，而且判斷一下是否權(quán)重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u];
const int N = 510;
int g[N][N];
int c1,c2;
int dist[N]; //dist[i]表示從出發(fā)點(diǎn)到i結(jié)點(diǎn)最短路徑的路徑長(zhǎng)度
int weight[N]; //每個(gè)城市救援隊(duì)數(shù)量
int w[N]; //w[i]表示從出發(fā)點(diǎn)到i點(diǎn)救援隊(duì)的數(shù)目之和
bool st[N];
int num[N]; //num[i]表示從出發(fā)點(diǎn)到i結(jié)點(diǎn)最短路徑的條數(shù)
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]){ //當(dāng)判定dis[u] + e[u][v] < dis[v]的時(shí)候，不僅僅要更新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]，而且判斷一下是否權(quán)重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); // 賦值無(wú)窮大
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
g[x][y] = g[y][x] = z; // 無(wú)向圖！所以存雙向信息
}
dij();
cout<<num[c2]<<" "<<w[c2];
}
參考鏈接：1003. Emergency (25)-PAT甲級(jí)真題（Dijkstra算法）文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-624430.html
到了這里，關(guān)于二、搜索與圖論6：Dijkstra 模板題+算法模板（Dijkstra求最短路 I, Dijkstra求最短路 II，1003 Emergency）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
