dp算法之有代价的最短路径

题目：有代价的最短路径

题目介绍：如下图所示，现在平面上有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 }

结果：