这是一道来自AcWing的题-850. Dijkstra求最短路 II，这里总结Dijkstra的两种方法。
1.原题链接>> 2.参考文章>>
1.朴素版，使用邻接矩阵
使用邻接矩阵的方法适合用于稠密图
注意和最小生成树Prim算法之间的关联
跳转到最小生成树Prim算法>>
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
const int MAXN=505;
const int INF=0x3f3f3f3f;
int w[MAXN][MAXN];
bool vis[MAXN];
int dist[MAXN];//集合到该点的最小距离
int Dijkstra(){//所有点初始化为无穷远memset(dist,0x3f,sizeof(dist));dist[1]=0;for(int i=1;i<=n;i++){//将n个点加入到已选集合中int t=-1;for(int j=1;j<=n;j++){if(!vis[j]&&(t==-1||dist[t]>dist[j])){t=j;}}// if(dist[t]==INF) return INF;//dijkstra不能在这里结束，因为有向图单向路径，存在dist[t]==INF且合法vis[t]=1;for(int j=1;j<=n;j++){dist[j]=min(dist[j],dist[t]+w[t][j]);}}if(dist[n] == 0x3f3f3f3f) return INF;return dist[n];
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){w[i][j]=INF;}}for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;w[a][b]=min(w[a][b],c);//有向图，不需要双向存储}int ans=Dijkstra();if(ans==INF) cout<<-1;else cout<<ans<<endl;
}
2.堆优化版
这种方法适合用于稀疏图
使用链式前向星来存储图
跳转到链式前向星>>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N=150010;
const int INF=0x3f3f3f3f;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
//h[i]表示第i个节点的起始idx
//e[idx]表示第idx条边的终点
//ne[idx]表示第idx条边的下一条边的idx
//w[idx]表示第idx条边的权值
int dist[N];
int vis[N];
void add(int x,int y,int c){//准备节点e[idx]=y;//这条边的终点w[idx]=c;//这条边的权值//头插法，这个节点的下一个节点指向h[x];ne[idx]=h[x];//更新新的头h[x]=idx++;
}
int Dijkstra(){memset(dist,0x3f,sizeof(dist));//在堆中的pair，第一个变量存距离，第二个变量存点，这样能够按照距离排序priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;heap.push({0,1});dist[1]=0;//!!!!!注意关键步骤while(!heap.empty()){pair<int,int>t=heap.top();heap.pop();if(vis[t.second]) continue;vis[t.second]=1;int idx=h[t.second];while(idx!=-1){if(dist[e[idx]]>t.first+w[idx]){dist[e[idx]]=t.first+w[idx];heap.push({dist[e[idx]],e[idx]});}idx=ne[idx];}}return dist[n];
}
int main(){memset(h,-1,sizeof(h));//初始化所有的h表示所有的链表都是空的。cin>>n>>m;while(m--){int x,y,c;cin>>x>>y>>c;add(x,y,c);}int ans=Dijkstra();if(ans==INF) cout<<-1;else cout<<ans<<endl;
}