dijkstra含路径输出

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

const int  N = 1001;

int n, m;


// 邻接矩阵
// 存点之间的距离
int g[N][N];

// 从源点到号点的距离
int dist[N];

// 标记其是否已经用于选取最短距离, 确定集
// 未被选取的自称为候选集
bool st[N];

// 朴素dijkstra()算法：适用全正边权,稠密图
// 贪心思想
// n次迭代 每次找最小值 更新距离
int dijkstra(){
    // 初始化所有距离为"正无穷", 源点(此处是1)为0
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 每次迭代都从候选集中选取一个最短路
    for (int i = 0; i < n - 1; 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 ++) {
            // 判断可不要？？ 更新与其连通的点？？
            if(g[t][j] != 0x3f3f3f3f) {
                dist[j] = min(dist[j], dist[t] + g[t][j]);
            }
        }

        // 将此点加入到确定集中
        // 表明其最短距离已经确定
        st[t] = true;
    }

    // 路径未被更新 说明不存在此路径
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

// 求最短路径法1(只能想到这种法子了)
// 在求最短路长度时，源点到号点的距离可能会被多次更新，不好操作
// 因此在所有距离被确定时，从终点反过来确定最短路
vector <int> v;
void path_s(){
    v.push_back(n);

    while(v.back() != 1){
        // 初始化为n保证dist[n]是最长的
        int mint = n;
        for(int i = 1; i <= n; i ++){
            // 连通 且 最短
            if(g[i][v.back()] != 0x3f3f3f3f && dist[mint] > dist[i])
                mint = i;
        }
        // 将路径加入
        v.push_back(mint);
    }
}


int main(){
    scanf("%d %d", &n, &m);

    // 初始化邻接矩阵
    memset(g, 0x3f, sizeof g);

    while(m --){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        // 对于正权可以消除自环及重边
        g[a][b] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());

    // 输出路径
    // path_s();
    // for(int i = v.size() - 1; i >= 0; i --){
    //     cout << v[i] << " ";
    // }



    return 0;
}