题目：有代价的最短路径
题目介绍：如下图所示，现在平面上有n个点，此时n=7，每个点可能和其他点相连，相连的线有一定权值，求出从0点到n-1点的消耗权值的最小值。
分析：用动态规划的思路来解决，每一点与其他点的消耗权值的最小值都储存在一个二维数组中，下一个点消耗的最小值可以根据前一个点来得出。如果两个点不相连，可以认为这两点的权值为无穷大。设一个二维数组初始化为无穷，再导入权值初始值，再用状态方程得出最小值储存在数组中。
状态方程：l[k][j] = min(l[k][j], l[k][i] + l[i][j])
我们可以得出0到n-1的最短路径表格：
| 距离 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 0 | 2 | 5 | 3 | 1 | 3 | 6 |
代码：
1 #include <iostream> 2 using namespace std; 3 int min(int a, int b); 4 int main() 5 { 6 int x = 99999; 7 int n = 7; 8 int i, j, k; 9 int **l = new int *[n]; 10 for (i = 0; i<n; i++) 11 { 12 l[i] = new int[n]; 13 } 14 for (i = 0; i < n; i++) 15 { 16 for (j = 0; j < n; j++) 17 { 18 l[i][j] = x; 19 } 20 } 21 l[0][1] = l[1][0] = 2; 22 l[1][2] = l[2][1] = 3; 23 l[2][6] = l[6][2] = 4; 24 l[0][3] = l[3][0] = 3; 25 l[3][6] = l[6][3] = 3; 26 l[0][4] = l[4][0] = 1; 27 l[4][5] = l[5][4] = 2; 28 l[5][6] = l[6][5] = 3; 29 for (k = 0; k < n; k++) 30 { 31 for (j = 0; j < n; j++) 32 { 33 for (i = 0; i < n; i++) 34 { 35 l[k][j] = min(l[k][j], l[k][i] + l[i][j]); 36 } 37 } 38 } 39 for (i = 1; i < n; i++) 40 { 41 cout << l[0][i] << endl; 42 } 43 } 44 int min(int a, int b) 45 { 46 if (a > b) 47 { 48 return b; 49 } 50 else { return a; } 51 }
结果：
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/611602.html