朴素dijsktra求最短路模版

核心思想
1. dist表示每个点到源点的最短距离，初始的源点可以改变
2. 维护一个点集合，，开始时集合中只有源点，每次从剩下的点中选一个到源距离最短的点，将其加入到集合中，表示已经求得最短距离
3. 用这个点更新其他所有点到源点的最短距离

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 100010, INF =0x3f3f3f3f;
int g[N][N];
int n, m;
int dist[N];  // 表示每个点到源点的最短路经长度
bool st[N];

void dijsktra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;  //源点可以改变

    for (int i = 0; i < n; i++) {

        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        st[t] = true;
        for (int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}


int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    for (int i = 1; i <= n; i++) g[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int a, b, v;
        cin >> a >> b >> v;
        g[a][b] = min(g[a][b], v);
    }

    dijsktra();

    if (dist[n] == INF) cout << -1 << endl;
    else cout << dist[n] << endl;

    return 0;
}