使用动态规划思想,利用「备忘录方法」实现对多段图问题进行编程求解。 输入格式: 第1行输入多段图顶点数m和边数n,以一个空格隔开。 依次输入n条边的信息,每行输入一边条的顶点编号及权重,以一个空格隔开。 输出格式: 第1行输出s到t的一条最短路径(路径结点以一个空格隔开),第2行输出此最短路径的长度。c++实现
时间: 2023-11-28 11:47:48 浏览: 24
以下是C++实现多段图问题的代码,使用了备忘录方法实现动态规划:
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 10010;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], q[N], hh, tt;
int f[N][N]; // 备忘录
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void spfa() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
q[tt ++] = 1;
while (hh != tt) {
int t = q[hh ++];
if (hh == N) hh = 0;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
q[tt ++] = j;
if (tt == N) tt = 0;
}
}
}
}
int dp(int u, int v) {
if (u > v) return 0;
if (u == v) return dist[u];
if (f[u][v] != -1) return f[u][v];
int res = 0x3f3f3f3f;
for (int i = u; i <= v; i++)
res = min(res, dp(u, i) + dp(i + 1, v));
return f[u][v] = res;
}
int main() {
memset(h, -1, sizeof h);
memset(f, -1, sizeof f);
cin >> n >> m;
while (m --) {
int a, b, c;
cin >> a >> b >> c;
for (int j = a; j < b; j++)
add(j, j + 1, 0); // 多段图建图技巧
add(a, b, c);
}
spfa();
cout << dp(1, n) << endl;
return 0;
}
```
需要注意的是,多段图问题需要对每个阶段中的所有点建立虚拟边,权重为0,以便在动态规划时使每个阶段中的点连通。