如题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;

//稠密图用邻接矩阵存储 g[i][j] = 2 代表i到j的距离为2
int g[N][N], dist[N], n, m;
bool st[N]; //标记当前迭代的点是否已经找到最短路

int dijkstra()
{
    //初始化第一个点到源点的距离，显然应该为1，那么我们就找到了“到源点的距离最近且未找到最短路的点”
    //之后的n次迭代就可以从第一个点开始
    dist[1] = 0;
    //注意这里不要把st[1] = 1,因为我们还没有开始迭代，如果st[1] = 1就丢失了第一个可迭代的点
    for (int i = 0; i < n; i ++) //这层循环只是为了进行n次迭代，里面的循环变量没有特殊意义
    {
        //从第一个点开始迭代，每次迭代找到“到源点的距离最近且未找到最短路的点”
        int t = -1; //用t记录这个点的编号
        for (int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        //!st[j]表示编号为j的点未找到最短路，t == -1是特判编号为1的点，因为之前没有迭代过其他点
        //dist[j] < dist[t] 是代表第j个点到源点的距离比第t个点短，经过n次迭代后t一定是到源点最近的点
        st[t] = true;
        //st[t] = true表示已经找到了到源点距离最近且未找到最短路的点
        //找到t这个点之后，我们要用这个点的最短路去更新t能到达所有点到源点的距离
        //这是一种局部最优的策略，在n次迭代后，dist[n]就一定是最短路！
        for (int k = 1; k <= n; k ++) //更新每个点的最短路
            dist[k] = min(dist[k], dist[t] + g[t][k]);
        //这样是对的吗？如果t到k没有边呢？
        //这种情况也是对的，因为如果t到k没有边那么取最小值肯定取得是dist[k]
    }
    //迭代n次后返回最短路
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    //初始化为无穷大
    memset(g, 0x3f, sizeof g);
    memset(dist, 0x3f, sizeof dist);
    cin >> n >> m;
    int a, b, c;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        {
            cin >> a >> b >> c;
            //处理有重边的情况，如果有重边就取最短的那条边
            g[a][b] = min(g[a][b],c);
        }
    cout << dijkstra();
    return 0;
}