$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路：

1. n = 500, m = 100000, 稠密图，适合用邻接矩阵
2. 迭代n次，每次都可以确定一个最短路的点
3. 每次取出距离 1 号点最近的点放入集合
4. 更新该点可以到达点所有点

完整代码（朴素版Dijkstra）

#include<bits/stdc++.h>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n,m;
int g[N][N],dist[N];
bool st[N];

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

    //迭代n次，每次确定一个最短路的点
    for(int i=0;i<n;i++)
    {
        //取出距离1最小的点
        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]==INF) return -1;
    return dist[n];
}

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

    //求Dijkstra更新距离时需要用到
    memset(g,0x3f,sizeof g);

    //建立邻接矩阵
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }

    cout<<dijkstra()<<endl;

    return 0;
}