朴素Dijkstra算法

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

#define N 501

int g[N][N],n,m,dis[N];
bool vis[N];

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

    memset(g,0x3f,sizeof g);

    for (int i = 1; i <= m; i++)
    {
        int x,y,z;
        cin >>x >>y >>z;
        g[x][y] = min(z,g[x][y]); 
    }

    memset(dis,0x3f,sizeof dis);
    dis[1] = 0;

    for (int i = 1; i <= n - 1; i++)
    {
        int now = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (!now || dis[j] < dis[now]))
                now = j;
        vis[now] = true;
        for (int j = 1; j <= n; j++)
            dis[j] = min(dis[j] , dis[now] + g[now][j]);
    }

    if (dis[n] == 0x3f3f3f3f)
        puts("-1");
    else
        cout <<dis[n];
    return 0;
}