算法竞赛进阶指南 849. Dijkstra求最短路 I（朴素算法，邻接矩阵）

#include
using namespace std;
const int N = 510;
int m, n, d[N], a[N][N];
bool v[N];
int main(){
    cin >> n >> m;
    memset(a, 0x3f, sizeof a);
    for(int i = 1; i <= m; i ++){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x][y] = min(a[x][y], z);
    }
    for(int i = 0; i <= n; i ++)
        a[i][i] = 0;
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int cnt = 1; cnt <= n; cnt ++){
        int x, minval = 0x3f3f3f3f;
        for(int i = 1; i <= n; i ++){ //找到未被标记的且dist[i]最小的点
            if(!v[i] && d[i] < minval)
                minval = d[i], x = i;
        }
        v[x] = true; //标记这个最小的点
        for(int y = 1; y <= n; y ++) //更新最小的边权和
            d[y] = min(d[y], d[x] + a[x][y]);
    }
    if (d[n] == 0x3f3f3f3f) puts("-1");
    else cout << d[n] << endl;
    
    return 0;
}