#include <iostream>

#include <stack>

using namespace std;

const int IDF = 1e7; //距离最大值

const int N = ; //点的数量最大值

int map[N][N]; //点与点之间的距离

int n; //点的数量

int m; //线的数量

int dist[N]; //源点到其他点的距离

bool flag[N]; //是否已加入找到集

int p[N]; //记录路径

void Dijkstr(int u); //计算距离

void findpath(int u);

int main() {

    int u, v, w; //起点 终点 权重

    cout << "请输入点的个数：";

    cin >> n;

    cout << "请输入线的数量：";

    cin >> m;

    //初始化

    for (int i = ; i < n; i++) {

        for (int j = ; j < n; j++) {

            map[i][j] = IDF;

        }

    }

    cout << "请输入两点及两点之间的距离：" << endl;

    while (m > ) {

        cin >> u >> v >> w;

        map[u][v] = min(w, map[u][v]);

        m--;

    }

    cout << "请输入起点：";

    cin >> u;

    cout << "信息输入完毕，开始计算地杰斯特拉距离" << endl;

    Dijkstr(u);

    findpath(u);

    return ;

}

void findpath(int u) {

     int temp;

     stack<int> s;

     cout<<"源点为："<<u<<endl;

     for(int i = ; i < n; i++){

         temp = p[i];

         while(temp != -){

             s.push(temp);

             temp = p[temp];

         }

         cout<<u<<"到"<<i<<"的距离为："<<dist[i]<<";路径为:";

         while(!s.empty()){

             cout<<s.top()<<"--";

             s.pop();

         }

         cout<<i<<endl;

     }

}

void Dijkstr(int u) {

    //初始化

    for (int i = ; i < n; i++) {

        dist[i] = map[u][i];

        flag[i] = false;

        if(dist[i] == IDF)

            p[i] = -;

        else

            p[i] = u;

    }

    //初始化起点

    dist[u] = ;

    flag[u] = true;

    for (int j = ; j < n; j++) {//找n次

        //从没有找到的点中找最近的

        int temp = IDF;

        int t = u;

        for (int i = ; i < n; i++) {

            if (flag[i] == false && dist[i] < temp) {

                temp = dist[i];

                t = i;

            }

        }

        if (t == u) { //没有找到 原距离不变

            return;

        }

        //更新距离 找到t点

        flag[t] = true;

        for (int i = ; i < n; i++) {

            if (flag[i] == false && map[t][i] + dist[t] < dist[i]) {

                dist[i] = map[t][i] + dist[t];

                p[i] = t;

            }

        }

    }

}