$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

朴素 Dijkstra。

1. 设 dist[1] = 0 和 dist[i] = INF。
2. 设集合 $S$ 为当前已确定最短路径的点。找出不在 $S$ 中且 dist 最小的点 $t$。
3. 用 $t$ 更新所有点的距离。

Dijkstra 的思想基于贪心。

本题是稠密图，因此可以用邻接矩阵存储。（当然链式前向星也可以）

时间复杂度 $O(n^2)$。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e5 + 10;
const long long INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx = 0;
int dist[N];
bool st[N];
int n, m;

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

void dijkstra() {
    for (int i = 1; i <= n; i++) dist[i] = INF, st[i] = 0;
    dist[1] = 0;
    for (int i = 0; i < n; i++) {
        int x = 0;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (dist[j] < dist[x] || x == 0)) x = j;
        }
        st[x] = 1;
        for (int j = h[x]; ~j; j = ne[j])
            dist[e[j]] = min(dist[e[j]], dist[x] + w[j]);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) h[i] = -1;
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    dijkstra();
    printf("%d\n", (dist[n] == INF) ? -1 : dist[n]);
    return 0;
}