原理：

看这里

代码：

稠密图：邻接矩阵

//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int dist[N]; //dist[i]表示结点i到起点的距离
int g[N][N]; //g[i][j]表示结点i到结点j的边的长度
bool st[N]; //st[i]表示该结点是否确定了最小距离，1是确定，0是未确定 
int n, m;
void Dijkstra(){
	memset(dist, 0x3f, sizeof(dist)); //把距离初始化为正无穷
    dist[1] = 0;
    int iter = n;
    while(iter--){ //n个点，循环n次
        int t = -1;
        //t随便初始化了一个不存在的结点，它最终用来存储未确定最小距离的结点，且该结点与其它结点相比目前到起点的距离最小
        for(int i = 1; i <= n; i++)
            if(st[i] == 0 && (t == -1 || dist[t] > dist[i]))
                t = i;   
        st[t] = true;
        //用结点t依次取更新其它结点到起点的距离，dist[i] = min(dist[i], dist[t] + g[t][i]);
        for(int i = 1; i <= n; i++)
            if(st[i] == 0)
                dist[i] = min(dist[i], dist[t] + g[t][i]);
                
    }
}
int main(){
	cin >> n >> m;
    memset(g, 0x3f, sizeof g);//将边先初始化为正无穷
    while(m--){
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);//存在重边
        //对于自环，不做处理，它不影响结果的计算
    }
    Dijkstra();
    if(dist[n] == 0x3f3f3f3f)
        cout << "-1" << endl;
    else
        cout << dist[n] << endl;
	return 0;
}

稀疏图：用邻接表

//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1.5e5 + 10;
int st[N];
int head[N];
int dist[N];
int e[N], ne[N], w[N], idx;//用来存边
int n, m;
//边:a->b,权重为c
void add(int a, int b, int c){
    e[idx] = b;
    ne[idx] = head[a];
    w[idx] = c;
    head[a] = idx;
    idx++;
}
void Dijkstra(){
    //图的遍历
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});//first表示距离，second表示结点
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    while(heap.size()){
        PII t = heap.top();
        heap.pop();
        int ver = t.second, d = t.first;
        if(st[ver] == 1) continue;
        st[ver] = 1;
        //a->b, 已知a的距离和边权，去更新b的距离
        for(int i = head[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > d + w[i]){
                dist[j] = d + w[i];
                heap.push({dist[j], j});
            }
        }    
    }
}
int main(){
	cin >> n >> m;//n个结点, m条边
    memset(head, -1, sizeof head);
    while(m--){
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    Dijkstra();
    if(dist[n] == 0x3f3f3f3f)
        cout << -1 << endl;
    else
        cout << dist[n] << endl;
	return 0;
}

样例输入：

3 3
1 2 2
2 3 1
1 3 4

样例输出：

3

解析：

堆优化

//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
struct Edge{
	ll v, w;
};
struct node{
	ll dis, u;
	bool operator>(const node& a) const { return dis > a.dis; }
};
priority_queue<node, vector<node>, greater<node> > q;
ll N, M, S, U, V, W, dis[100005], vis[100005];
vector<Edge> G[100005];
void dijkstra(){
	for(int i = 1; i <= N; i++) dis[i] = 2147483647;
	memset(vis, 0, sizeof(vis));
	dis[S] = 0;
	q.push({0, S});
	while(!q.empty()){
		int u = q.top().u;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto nod : G[u]){
			int v = nod.v, w = nod.w;
			if (dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				q.push({dis[v], v});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> S;
	for (int i = 1; i <= M; i++){
		cin >> U >> V >> W;
		G[U].push_back({V, W});
	}
	dijkstra();
	for (int i = 1; i <= N; i++) cout << dis[i] << " ";
	return 0;
}

题目

P3371 【模板】单源最短路径（弱化版） - 洛谷