程序填空题：多段图问题（动态规划法）

多段图问题。在A处有一水库，现需要从A点铺设一条管道到E点，边上的数字表示与其相连的两个地点之间所需修建的管道长度。现要找出一条从A到E的修建线路，使得所需修建的管道长度最短。


```c++
//逆推法
#include
using namespace std;
const int N = 20;
const int MAX = 1000;
int arc[N][N];
int Backpath(int n);
int creatGraph();
int main()
{
int n = creatGraph( );
int pathLen = Backpath(n);
cout< return 0;
}
int creatGraph()
{
int i, j, k;
int weight;
int vnum, arcnum;
cin>>vnum>>arcnum;
for (i = 0; i < vnum; i++)
for (j = 0; j < vnum; j++)
arc[i][j] = MAX;
for (k = 0; k < arcnum; k++)
{
cin>>i>>j>>weight;
arc[i][j] = weight;
}
return vnum;
}
int Backpath(int n)
{
int i, j, temp;
int cost[N];
int path[N];
for(i = 0; i < n; i++)
{
cost[i] = MAX;
path[i] = -1;
}
cost[0] = 0;
for(j = 1; j < n; j++)
{
for(i = j - 1; i >= 0; i--)
{
if ()
{
;
= i;
}
}
}
return ;
}
```
### 输入格式:

第一行输入多段图顶点数m和边数n。依次输入n条边的信息，每行输入一边条的顶点编号及权重。


### 输出格式:

输出最短路径。

### 输入样例1:

```in
10 19
0 1 2
0 2 4
0 3 3
1 4 7
1 5 4
2 4 3
2 5 2
2 6 4
3 4 6
3 5 2
3 6 5
4 7 3
4 8 4
5 7 6
5 8 3
6 7 3
6 8 3
7 9 3
8 9 4
```

### 输出样例1:

```out
12
```





答案：
第1空：arc[i][j] + cost[i] < cost[j]

第2空：cost[j] = arc[i][j] + cost[i]

第3空：path[j]

第4空：cost[n-1]