原理：

看这里

代码：

稠密图：邻接矩阵

//顶级垃圾程序
//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

解析：