[单源最短路+路径还原]城市交通路网 HUSTOJ2813
程序员文章站
2022-07-14 21:38:46
...
题目描述
下图表示城市之间的交通路网,线段上的数字表示费用,单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。
如图:求v1到v10的最短路径长度及最短路径。
输入
第一行为城市的数量N;
后面是N*N的表示两个城市间费用组成的矩阵。
输出
A->E的最省费用。
样例输入
10
0 2 5 1 0 0 0 0 0 0
0 0 0 0 12 14 0 0 0 0
0 0 0 0 6 10 4 0 0 0
0 0 0 0 13 12 11 0 0 0
0 0 0 0 0 0 0 3 9 0
0 0 0 0 0 0 0 6 5 0
0 0 0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
样例输出
minlong=19
1 3 5 8 10
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n;
int cost[500][500];
int d[500];
bool vis[500];
int qiandao[500]; //存储路径
void dij(int s) //迪杰斯特拉算法 单源最短路
{
memset(vis,0,sizeof(vis));
memset(qiandao,0,sizeof(qiandao));
fill(d+1,d+n+1,inf);
d[1]=0;
while(1)
{
int v=0;
for(int u=1;u<=n;u++)
if(!vis[u]&&(!v||d[u]<d[v])) v=u;
if(!v) break; //不存在u
vis[v]=1; //v计算过
for(int u=1;u<=n;u++)
if(d[u]>d[v]+cost[v][u])
{d[u]=d[v]+cost[v][u];qiandao[u]=v;}
}
}
int main()
{
while(cin>>n)
{
stack<int>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>cost[i][j];
if(!cost[i][j]) cost[i][j]=inf; //不连通
}
dij(n); //求到n的最短路
cout<<"minlong="<<d[n]<<endl;
int u=n;
while(u)
{
q.push(u);
u=qiandao[u];
} //倒序输出
cout<<q.top();q.pop();
while(!q.empty())
{
cout<<' '<<q.top();
q.pop();
}
cout<<endl;
}
return 0;
}