动态规划法求单源最短路径问题 c++

以下是使用动态规划法求单源最短路径问题的C++代码示例：

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

const int INF = 0x3f3f3f3f; // 表示正无穷

int main() {
    int n, m, s; // n表示节点数，m表示边数，s表示起点
    cin >> n >> m >> s;

    int dist[n + 1]; // 存储起点到各个节点的最短距离
    bool vis[n + 1]; // 标记节点是否已经被访问过
    int edge[n + 1][n + 1]; // 存储边的权值

    memset(dist, INF, sizeof(dist)); // 初始化dist数组为正无穷
    memset(vis, false, sizeof(vis)); // 初始化vis数组为false
    memset(edge, INF, sizeof(edge)); // 初始化edge数组为正无穷

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u][v] = w; // 存储边的权值
    }

    dist[s] = 0; // 起点到自己的距离为0

    for (int i = 1; i <= n; i++) {
        int k = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (k == 0 || dist[j] < dist[k])) {
                k = j;
            }
        }
        vis[k] = true;
        for (int j = 1; j <= n; j++) {
            if (edge[k][j] < INF) {
                dist[j] = min(dist[j], dist[k] + edge[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << dist[i] << " ";
    }
    cout << endl;

    return 0;
}