朴素的写法

int dijkstra()
{
    memset(dist, INF, sizeof(dist));
    dist[1] = 0; //从1号点开始

    for(int i = 1; i <= n; i++){ //依次把顶点加入集合S
        int minw = INF, u;
        for(int j = 1; j <= n; j++){
            if(!in[j] && dist[j] < minw){
                u = j;
                minw = dist[j];
            }
        } //选出不在S中且路径最短的点u
        in[u] = 1; //让点u加进去
        for(int j = 1; j <= n; j++){ //如果经过点u能走出来更短的，则更新dist
            if(!in[j] && dist[u] + g[u][j] < dist[j])
                dist[j] = dist[u] + g[u][j];
        }
    }

    if(dist[n] == INF) return -1;
    else return dist[n];
}

y总的写法：更加简洁

1. 外层for循环：是为了进行n次，想都加进来
2. t是存当前节点的临时变量
3. 每次选择下一条最短路的时候，什么样的点可以加进来？没加进来且后续dist比t更小的（或者第一次选的）。
4. 这样简洁的写法其实会把非联通点加进来。但是不影响，距离仍是INF
5. 更新时，这里不判断是否in[i]也没事，因为如果点已经在集合S中了，dist[j]肯定是最小的，不会改变。

int dijkstra()
{
    memset(dist, INF, sizeof(dist));
    dist[1] = 0;//初始化，从1开始

    for(int i = 1; i <= n; i++){ 
        int t = -1; //当前路径最短的点
        for(int j = 1; j <= n; j++)
            if(!in[j] && (t == -1 || dist[j] < dist[t])) 
                t = j; 
        in[t] = 1;
        for(int j = 1; j <= n; j++) 
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    if(dist[n] == INF) return -1;
    else return dist[n];
}

主函数：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 510;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
int in[N]; //in[i] = 1表示节点i已被选进集合S，最短路已确定

int dijkstra();

int main()
{
    cin >> n >> m;
    memset(g, INF, sizeof(g));
    while(m--){
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
//        if(g[x][y]) g[x][y] = min(g[x][y], z); //重边选最小的
//        else g[x][y] = z;
    }
    cout << dijkstra() << endl;
}