分析

Dijkstra算法，求一个点到各个点分别的最短距离，
可以将所有顶点分为两部分，一是最短路径集合，另一个是其他点的集合。
用一个一维数组来联系这两个集合，这个数组存的当前点到其他点的最短距离。
int t = - 1;
for(int j = 1; j <= n; j ++ )
if(!st[j]&&(t==-1||dist[t] > dist[j]))
t = j;
通过这个循环可以得到目前集合中一条最短路径（可证明，这里就不证了）
然后将这个点加入最短路径集合，并利用这条最短路径的长度来更新其他未在最短路径集合中的点到
顶点的距离，直到找到全部的最短路径。

(最短路径算法) $O(n^2)$

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510,INF = 0x3f3f3f3f;
int g[N][N];
int dist[N];
bool  st[N];
int n,m;
int Dijkstra()
{
    memset(dist,INF ,sizeof dist);
    dist[1] = 0;
    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;

        for(int j = 1 ; j <= n; j ++ )
         dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }
    if(dist[n] == INF ) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    memset(g,INF,sizeof g);
    for(int i = 0; i < m; i ++ )
    {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c);
    }

    cout << Dijkstra();

    return 0;
}