一本通1261: 城市交通路网
【题目描述】
下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。
如图：求v1到v10的最短路径长度及最短路径。
【输入】
第一行为城市的数量N;
后面是N*N的表示两个城市间费用组成的矩阵。
【输出】
A->E的最省费用。
【正文】
我认为，一道非常简单的DP，刚学的新手都能想到。。。
状态转移方程 ：dp[j] = dp[i] + a[i][j]
代码
#include
using namespace std;int n, a[510][510], dp[510], p[510];
int ans[510], top = 0;void vis(int t) { // 递 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！