模板题目描述如下
我们之前找最短路，dfs时间可能超时（大暴力枚举），而bfs只能解决边权为1的情况，而且也算是枚举（小暴力枚举），有没有什么算法能解决含边权的最短路问题呢？这里引入Dijkstra算法，同时是常考的一个算法（等我自己写出来zzu2024招新赛b题我结合考题讲一下），很有学习的必要
该算法的核心就是迭代遍历n次dist数组（所有未确定值的节点到原点的最小值），每找到更小的距离，用t变量记录更新最小距离，并在每次迭代完成，确定又一个点到原点的最小距离后，用该距离更新其他未确定到原点最小值的节点的最小值
觉得难以理解的八成是临界表或邻接矩阵学的出现问题，算法本身的思想很简单。以下给出两种数据结构的实现方式，大多情况下用邻接表，但本题是稠密图，用邻接矩阵查找效率会快一点
ps：举个例子说明稠密图和稀疏图怎么区分
N个节点，如果每个节点都相互连接，若为无向图，则有CN 2，即 N*(N-1)/2 条边，若为有向图，则有 N*(N-1)条边。若题目给的是有向图，给定n，m的值，若m大于n*（n-1），则为稠密图；若小于n*（n-1），则为稀疏图。无向图同理
本题有向图给的数据n=500，m=1e5；n^2就是2.5e5>m，所以判断为稠密图，用邻接表能写，就是存数据的时候效率比矩阵低，要是会邻接矩阵的写法推荐换一种写法
刚好可以对比学习一下不同存储结构遍历和使用的方式，加深对图的理解应用
用临界表存储图的代码如下 （清晰的图解）：AcWing 849. Dijkstra求最短路 I：图解 详细代码（图解） - AcWing）
#include <bits/stdc++.h>
using namespace std;
const int N=510,M=1e5+10;
int e[M],ne[M],w[M],idx,h[N];
bool check[N];//记录该点是否已经是所有情况下的最小值
int dist[N];//每个点到原点的距离
int n,m;
void add(int a,int b,int ww){//这里就对应到了之前说的e数组可以扩展成多种,存多种值,如v，w等(由于和e是平行关系且也是存值)
e[idx]=b;w[idx]=ww;ne[idx]=h[a];h[a]=idx++;
}
//核心--Dijkstra
void Dijkstra(){
memset(dist,0x3f,sizeof dist);//初始所有点到原点距离为无穷
dist[1]=0;//初始化原点到自身距离为零
for(int i=0;i<n;i++){//对所有的节点都要确定一次离原点的最短距离 ,迭代n次
int t=-1;/*要初始化一个dist数组的值为无穷大，但不能真的取dist里的元素（要遍历dist），只能曲线救国，用临时变量取一个随机值（这里取-1，取其他也行，特判条件对应着改了），再对该值进行特判*/
for(int j=1;j<=n;j++){//遍历其他所有未确定最小值的节点（state【j】==0），寻找更短的距离 ，即dist数组的最小值
if(check[j]==false&&(dist[j]<dist[t]||t==-1)){
t=j;
}
}
check[t]=1;
//用新找到的已确定的值从新刷新各个点到原点距离
for(int j=h[t];j!=-1;j=ne[j]){
int temp=e[j];
dist[temp]=min(dist[temp],dist[t]+w[j]);/当前存储距离和新找到的距离+新点到j的距离取最小*/
}
}
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++){
int a,b,ww;
cin>>a>>b>>ww;
add(a,b,ww);//将b存入a的链表中，并记录权重（边长）为w
}
Dijkstra();
if(dist[n]!=0x3f3f3f3f) cout<<dist[n];/*若为无穷大，则没被更新过，即原点到不了该点，输出-1*/
else cout<<"-1";
}用临界矩阵存储图的代码如下 ：
#include <bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool check[N];
int n,m;
void Dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(check[j]==0&&(t==-1||dist[j]<dist[t])){
t=j;
}
}
check[t]=true;
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
}
int main(){
memset(g,0x3f,sizeof g);
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
Dijkstra();
if(dist[n]!=0x3f3f3f3f) cout<<dist[n];
else cout<<-1;
}
