邻接矩阵版本

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;//n是点的个数，m是边的个数
int g[N][N];//存储图中每个点之间的距离,g[i][j]表示结点i指向结点j的距离，初始化是无穷大
int dist[N];//存储每个点到1的距离, 最终答案存储在这。
bool st[N];//已确定了最短路径的点，加入s集合，状态为true,初始化所有的结点都是false

int dijkstra()
{
    //初始化距离
    memset(dist, 0x3f, sizeof dist);//初始化每个结点到起点1的距离，无穷大
    dist[1] = 0;//自己到自己是0

    //迭代n次
    for (int i = 0; i < n; i ++ )//迭代n次，每次放一个结点入s集合，n次放完n个
    {
        //第一步：找到t <- 没加入s集合，且距离起点最近的点
        int t = -1;//即将加入s集合的结点编号,非1..n范围内都可以选
        for (int j = 1; j <= n; j ++ )//遍历结点编号1..n
            if(!st[j] && (t == -1 || dist[j] < dist[t]))//没加入s集合，且距离起点最近的点-> t
                t = j;                                  //t == -1 代表第一次找到没加入集合的点，不管三七二十一，先加入为尊，实在是妙~

        //第二步：结点t加入s集合
        st[t] = true; 

        //第三步：用t来更新其他点到起点的距离
        for (int j = 1; j <= n; j ++ )//松弛操作：用t来更新其他点到起点的距离,也就是看t作为中间点，有没有可能减距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    else dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);//初始化每个点之间距离无穷大

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);//不用特判自环，边权都是正整数，自环不会对最短路径有影响。
        g[a][b] = min(g[a][b], c); // min的作用是消除重边，有重边取最短的即可-目的是求最短路径
    }

    printf("%d\n", dijkstra());

    return 0;
}

邻接表版本

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;

int h[N], w[M], e[M], ne[M], idx;
int n, m;
int dist[N];
bool st[N];

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

int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 1; i <= n; i ++ )
    {
        int k = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (k == -1 || dist[j] < dist[k]))
                k = j;
        st[k] = true;

        for (int t = h[k]; t != -1; t = ne[t])
        {
            int j = e[t];
            dist[j] = min(dist[j], dist[k] + w[t]);
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    cout << Dijkstra() << endl;

    return 0;
}