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

动态规划法是解决单源最短路径问题的一种有效方法。下面是使用C++实现动态规划法求解单源最短路径问题的示例代码：

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

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n, m, s, t;
int dis[MAXN], vis[MAXN];
int edge[MAXN][MAXN];

void dijkstra(int s) {
    memset(vis, 0, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    for (int i = 1; i <= n; i++) {
        int k = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (k == -1 || dis[k] > dis[j])) {
                k = j;
            }
        }
        vis[k] = 1;
        for (int j = 1; j <= n; j++) {
            dis[j] = min(dis[j], dis[k] + edge[k][j]);
        }
    }
}

int main() {
    cin >> n >> m >> s >> t;
    memset(edge, INF, sizeof(edge));
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u][v] = min(edge[u][v], w);
    }
    dijkstra(s);
    cout << dis[t] << endl;
    return 0;
}

其中，n表示图中的节点数，m表示图中的边数，s表示起点，t表示终点，edge[i][j]表示节点i到节点j的边权值。在代码中，我们使用了dijkstra算法来求解单源最短路径问题。具体来说，我们首先初始化dis数组和vis数组，然后从起点开始，每次找到一个未访问的距离最短的节点k，将其标记为已访问，并更新与其相邻的节点的距离。最终，dis数组中存储的就是起点到各个节点的最短距离，dis[t]即为起点到终点的最短距离。