#include <bits/stdc++.h>

using namespace std;

// 原始文档：https://www.cnblogs.com/xzxl/p/7246918.html
#pragma region SPFA算法模板
// 最短路径——SPFA算法

// 最大值
// https://blog.csdn.net/jiange_zh/article/details/50198097
/**
如果我们想要将某个数组清零，我们通常会使用memset(a,0,sizeof(a))，方便又高效，但是当我们想将某个数组全部赋值为无穷大时，
就不能使用memset函数而得自己写循环了，因为memset是按字节操作的，它能够对数组清零是因为0的每个字节都是0（一般我们只有赋值为-1
和0的时候才使用它）。现在好了，如果我们将无穷大设为0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f的每个字节都是0x3f！所以要把一段
内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。所以在通常的场合下，0x3f3f3f3f真的是一个非常棒的选择！
*/
const int INF = 0x3f3f3f3f;

// https://www.cnblogs.com/xzxl/p/7246918.html
int matrix[100][100];  //邻接矩阵
bool visited[100];     //标记数组
int dist[100];         //源点到顶点i的最短距离
int path[100];         //记录最短路的路径
int enqueue_num[100];  //记录入队次数
int vertex_num;        //顶点数
int edge_num;          //边数
int source;            //源点

bool SPFA() {
    memset(visited, 0, sizeof(visited));
    memset(enqueue_num, 0, sizeof(enqueue_num));
    for (int i = 1; i <= vertex_num; i++) {
        dist[i] = INF;
        path[i] = source;
    }
    queue<int> Q;
    Q.push(source);
    dist[source] = 0;
    visited[source] = 1;
    enqueue_num[source]++;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        visited[u] = 0;
        for (int v = 1; v <= vertex_num; v++) {
            if (matrix[u][v] != INF)  //u与v直接邻接
            {
                if (dist[u] + matrix[u][v] < dist[v]) {
                    dist[v] = dist[u] + matrix[u][v];
                    path[v] = u;
                    if (!visited[v]) {
                        Q.push(v);
                        enqueue_num[v]++;
                        if (enqueue_num[v] >= vertex_num)
                            return false;
                        visited[v] = 1;
                    }
                }
            }
        }
    }
    return true;
}

void Print() {
    for (int i = 1; i <= vertex_num; i++) {
        if (i != source) {
            int p = i;
            stack<int> s;
            cout << "顶点 " << source << " 到顶点 " << p << " 的最短路径是： ";
            while (source != p)  //路径顺序是逆向的，所以先保存到栈
            {
                s.push(p);
                p = path[p];
            }
            cout << source;
            while (!s.empty())  //依次从栈中取出的才是正序路径
            {
                cout << "--" << s.top();
                s.pop();
            }
            cout << "    最短路径长度是：" << dist[i] << endl;
        }
    }
}

#pragma endregion SPFA算法模板

int main() {
    //输入+输出重定向
    freopen("../MiniPath/SPFA.txt", "r", stdin);

    cout << "请输入图的顶点数，边数，源点：";
    cin >> vertex_num >> edge_num >> source;
    for (int i = 1; i <= vertex_num; i++)
        for (int j = 1; j <= vertex_num; j++)
            matrix[i][j] = INF;  //初始化matrix数组
    cout << "请输入" << edge_num << "条边的信息：\n";
    int u, v, w;
    for (int i = 1; i <= edge_num; i++) {
        cin >> u >> v >> w;
        matrix[u][v] = w;
    }
    if (SPFA())
        Print();
    else
        cout << "对不起，存在负权图，不能使用本算法!" << endl;
    //关闭文件
    fclose(stdin);
    return 0;
}