算法

朴素dijkstra算法

时间复杂是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

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

思路

Dijkstra 的整体思路比较清晰
即进行n（n为n的个数）次迭代去确定每个点到起点的最小值 最后输出的终点的即为我们要找的最短路的距离

所以按照这个思路除了存储图外我们还需要存储两个量

dist[n] //用于存储每个点到起点的最短距离
st[n]   //用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新

每次迭代的过程中我们都先找到当前未确定的最短距离的点中距离最短的点
（至于为什么是这样那么这就涉及到Dijkstra算法的具体数学证明了 有兴趣的同学可以百度一下）

int t=-1;       //将t设置为-1 因为Dijkstra算法适用于不存在负权边的图
for(int j=1;j<=n;j++)
{
    if(!st[j]&&(t==-1||dist[t]>dist[j])    //该步骤即寻找还未确定最短路的点中路径最短的点
        t=j;
}
通过上述操作当前我们的t代表就是剩余未确定最短路的点中 路径最短的点
而与此同时该点的最短路径也已经确定我们将该点标记

st[t]=true;

然后用这个去更新其余未确定点的最短距离

for(int j=1;j<=n;j++)
    dist[j]=min(dist[j],dist[t]+g[t][j]);
//这里可能有同学要问j如果从1开始的话 会不会影响之前已经确定的点的最小距离
//但其实是不会 因为按照我们的Dijkstra算法的操作顺序 先确定最短距离的点的距离已经比后确定的要小 所以不会影响
//当然你也可以在循环判断条件里加上if(!st[i])
//这里j从1开始只是为了代码的简洁

进行n次迭代后最后就可以确定每个点的最短距离
然后再根据题意输出相应的 要求的最短距离

C++ 代码

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

using namespace std;

const int N = 510;
int n, m;
int g[N][N]; //稠密图一般使用邻接矩阵
int dist[N]; //记录每个节点距离起点的距离
bool st[N]; //True表示已经确定最短路 属于s集合

int dijkstra() {
    //所有节点距离起点的距离初始化为无穷大
    memset(dist, 0x3f, sizeof dist);
    //起点距离自己的距离为零
    dist[1] = 0;

    //迭代n次，每次可以确定一个点到起点的最短路
    for (int i = 0; i < n; ++i) {
        int t = -1;
        //t的作用？

        for (int j = 1; j <= n; ++j) {
            //不在s集合，并且
            //如果没有更新过，则进行更新， 或者发现更短的路径，则进行更新
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }

        //加入到s集合中
        st[t] = true;

        //找到了距离最小的点t，并用最小的点t去更新其他的点到起点的距离
        for (int j = 1; j <= n; ++j) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }

    // 如果起点到达不了n号节点，则返回-1
    if (dist[n] == 0x3f3f3f3f) return -1;
    // 返回起点距离n号节点的最短距离
    return dist[n];
}

int main() {
    cin >> n >> m;
    //所有节点之间的距离初始化为无穷大
    memset(g, 0x3f, sizeof g);
    // 0x3f 0x3f3f3f3f 的区别？

    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c); //如果有重边，请保留权值最小的一条边
    }

    cout << dijkstra() << endl;

    return 0;
}