最短路径问题（单源最短路问题-都正边）1.0

基本思路和代码来自y总!

朴素版dijkstra算法

适合与稠密图，用邻接矩阵来存图

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;

int n,m;//
int g[520][520];//存图边的值 
int dist[520];//存最短距离 
bool st[520];//是否已经遍历过最小的边 

int dijkstra(){
	memset(dist,0x3f,sizeof(dist));//思路：1.将所有的距离初始化为无穷大 
	dist[1]=0;//思路: 2.将节点1的距离初始化为0 
	
	for(int i=0;i<n;i++){//思路: 3.遍历所有的节点 
		int t=-1;
		for(int j=1;j<=n;j++)//思路: 4.找到所有未遍历过的点中距离最短的 
			if(!st[j] && (t==-1 || dist[t]>dist[j]))//判断是否为最短的 
				t=j;
		//if(t==n) break;		
		st[t]=true;//记录已经用过 
		
		for(int j=1;j<=n;j++)//思路: 5.用t去更新每个节点的最短距离 
			dist[j]=min(dist[j],dist[t]+g[t][j]);
	}
	
	if(dist[n]==0x3f3f3f3f) return -1;
	else return dist[n];
}

int main(){
	cin>>n>>m;
	
	memset(g,0x3f,sizeof(g));
	
	while(m--){//输入图 
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c);//多条边，每次只取最小的那条边 
	}
	
	int  t=dijkstra();
	cout<<t; 
}

堆优化版的dijkstra算法

适用于稀疏图，用邻接表来存图

#include<bits/stdc++.h>
#include<queue>

using namespace std;
const int N=100010;
typedef pair<int,int>PII; 
int n,m,idx;
int h[N],e[N],ne[N],w[N];
int dist[N];
bool st[N];

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

int dijstra(){
	memset(dist,0x3f,sizeof(dist));//照样初始化 
	dist[1]=0; 
	
	priority_queue<PII,vector<PII>,greater<PII>> heap;//创建堆 
	heap.push({0,1});//将第一个点推入 
	
	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;
	else return dist[n];
}

int main(){
	cin>>n>>m;
	memset(h,-1,sizeof(h));
	
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c); 
	}
	
	int  t=dijstra();
	cout<<t; 
}