<—点个赞吧QwQ

宣传一下算法基础课整理{:target=”_blank”}

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 $1$ 号点到 $n$ 号点的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，则输出 $\-1$。

输入格式

第一行包含整数 $n$ 和 $m$。

接下来 $m$ 行每行包含三个整数 $x,y,z$，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$。

输出格式

输出一个整数，表示 $1$ 号点到 $n$ 号点的最短距离。

如果路径不存在，则输出 $\-1$。

数据范围

$1 \\le n \\le 500$,
$1 \\le m \\le 10^5$,
图中涉及边长均不超过10000。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

思路

$\text{Dijkstra}$的整体思路比较清晰
即进行$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次迭代后最后就可以确定每个点的最短距离
然后再根据题意输出相应的要求的最短距离

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N =510,M = 100010;
int n,m;
int dist[N];
bool st[N];
int g[N][N];
int main () {
    cin >> n >> m;
    memset (g,0x3f,sizeof (g));
    while (m--) {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = min (g[a][b],c);
    }
    memset (dist,0x3f,sizeof (dist));
    dist[1] = 0;
    for (int i = 1;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]);
    }
    if (dist[n] == 0x3f3f3f3f) puts ("-1");
    else cout << dist[n] << endl;
}