城市交通路网c++

解题思路:/*思路分析：

动归的方向有两种，一种由A->E，另一种则由E->A

这题要使用哪一种？

关键在于输出中 “第二行 A->E的最短路径。”

如果从A出发，根本不肯能记录下最短路径，因为dp[i]只记录了由起点A到当前点i的最短距离，

而无法判断其最终最短路径是哪一条

所以，我们只能使用逆推的方式

即 dp[i]记录了由i点到终点E的最短距离

再使用数组index去记录每一次由i点到终点最短距离的路径

最后从点A出发 即i=1出发，输出index[i]的值，且i的值更新为index[i]的值

这样输出的index[i]便是每一个点通往终点的最小值的下一个点。

*/

注意事项:

参考代码:

#include<bits/stdc++.h>

#define N 1000005;

using namespace std;

int f[1005][1005];//存储路径图，不知道n的范围，尽量大就好 

int dp[1005];

int index[1005];//后序节点

int main()

{

int n;

cin>>n;

for(int i=1;i<=n;i++)

{

for(int j=1;j<=n;j++)

{

cin>>f[i][j];

}

}

dp[n]=0;//终点通往自己的路径长为0，动归模板的关键之一！！！

for(int i=1;i<n;i++)

dp[i]=N;//无限远 

for(int i=n-1;i>0;i--)

{

for(int j=i+1;j<=n;j++)

{

if(f[i][j]!=0&&dp[j]+f[i][j]<dp[i])//确定i点到终点的最短路径

{

dp[i]=dp[j]+f[i][j];

index[i]=j;//确定i点到终点的最短路径

}

}

}

cout<<"minlong"<<dp[1]<<endl;//确定i点到终点的最短路径

int flog=1;

while(flog){

cout<<flog<<" ";

flog=index[flog];

}

return 0;

}