朴素Dijkstra算法

算法思想：

将所有距离起点的距离初始化为0x3f，随后更新起点到自己的距离为0，在迭代n次或者n-1次的过程中不断更新图中不同点到起点的距离，在每次迭代过程中都要求找到一个距离上次插入的元素最近的点，随后将这个点的位置信息进行更新，依据这个点再次更新图中所有点到起点的距离

注意事项：

1. 由于该图为稠密图，因此要使用邻接矩阵的方法来进行存储；
2. 在迭代的过程中，迭代n次或者n-1次都是可以的，但是两种代码之间有循环条件方面的差别，原理在于迭代n-1次的时候已经确定了第n个点到起点的距离为最短路；
3. 在找到相应的t之后要对位置信息进行更新；
4. 在寻找t的过程中又有一层嵌套的循环和判断条件，这里是为了在所有点中找到距离起点最近且没有被装入集合的点，将其装入集合，更详细的理解可以自己画图解决；

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

using namespace std;
const int N = 510;
//设置输入图中点的个数和边的数量
int n,m;
//二维数组g用来实现邻接矩阵，g[a][b]表示a节点到b节点的距离
int g[N][N];
//dist数组用来存储不同点到第一个点的距离
int dist[N];
//st数组用来存储这个节点有没有被使用过
bool st[N];

//dijkstra算法的具体实现方法
int dijkstra(){
    //首先对dist数组进行更新
    memset(dist,0x3f,sizeof dist);
    //设置dist数组的第一个节点到自己的距离为0
    dist[1]=0;

    //???为什么这里要进行n次循环
    for(int i=0;i<n-1;i++){
        //1. 找到距离当前节点

        //???这个t的作用是什么
        int t=-1;
        //对图中的每个节点进行遍历
        for(int j=1;j<=n-1;j++){
            //如果当前遍历到的位置元素没有加入集合，并且它到1号点的距离在所有点中最小，比如1号点出去连接了2号点和3号店
            //同时还有四号点，这一步的一定会找到距离1号店距离最近的点
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        }

        //2. 将找到的t插入数组
        st[t]=true;

        //3. 利用找到的最近的点更新所有点到1号点的最短距离
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    if(dist[n]==0x3f3f3f3f)     return -1;
    return dist[n];
}

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

    //对g数组进行更新，任何两个点之间的距离都是正无穷
    memset(g,0x3f,sizeof g);

    while (m -- ){
        //开始输入不同点之间的距离，对邻接矩阵进行更新
        int a,b,c;
        scanf("%d %d %d", &a, &b,&c);
        g[a][b]=min(g[a][b],c);
    }
    int t=dijkstra();
    cout<<t;

    return 0;
}

迭代n次代码：

#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];

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

    //为什么这里使用n-1就可以ac
    for(int i=0;i<n;i++){

        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                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)     return -1;
    return dist[n];
}

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

    memset(g,0x3f,sizeof g);

    while (m -- ){
        int a,b,c;
        scanf("%d %d %d", &a, &b,&c);
        g[a][b]=min(g[a][b],c);
    }
    int t=dijkstra();
    cout<<t;

    return 0;
}