迪杰斯特拉（模板）

#include<iostream>
using namespace std;
const int N = 1005;
int Map[N][N];//邻接矩阵存图
int dis[N],vis[N];//dis存储的是起点到i点的最短路，vis用于标记是否被访问过 
//开始迪杰斯特拉！！！ 
void dij(int n,int s){
	//初始化一个极大值给dis，后面用于更新 
	for(int i=0;i<=n;i++) dis[i]=1e9;
	dis[s] = 0;//起点到自己的距离为0
	//进行n次遍历顶点，找到所有点的最短路
	for(int i=1;i<=n;i++){
		int u=0;
		//①在未访问过的点中，选择距离起点最短的点u
		for(int j=1;j<=n;j++){
			if(dis[j]<dis[u] && !vis[j]){
				u = j;
			}
		} 
		vis[u]=1;//标记节点u的最短路已经找到！！！！！！！！！
		//②更新从节点u到其他没有被访问的点的最短距离
		for(int j=1;j<=n;j++){
			if(Map[u][j]){//如果点u到j有边 
				int v = j;
				int w = Map[u][j];
				//如果点j这条边更短了！！！做松弛！ 
				if(dis[v]>dis[u]+w){
					dis[v] = dis[u]+w;
				}
			}
		} 
	} 
} 

int main(){
	int n,m,s;//节点的数量、边数、起点 
	cin>>n>>m>>s;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		
//		if(Map[u][v]){
//			tmp = Map[u][v];
//		}else{
//			Map[u][v] = 1e9;
//			tmp = Map[u][v];
//		}
		//处理可能出现重边的情况，无所谓，我只要最短的！		
		int tmp = Map[u][v]?Map[u][v]:1e9;
		Map[u][v] = min(tmp,w);
	}
	
	dij(n,s);//传入顶点数和起点，开始迪杰斯特拉算法！！！！！！ 
	
	// 输出结果
	for(int i=1;i<=n;i++){
		if(dis[i]!=1e9){
			cout<<dis[i]<<" ";
		}else{
			cout<<"-1"<<" ";//节点不可达 
		}
	} 
	
	return 0;
}