欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[单源最短路+路径还原]城市交通路网 HUSTOJ2813

程序员文章站 2022-07-14 21:38:46
...

题目描述

下图表示城市之间的交通路网,线段上的数字表示费用,单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。

[单源最短路+路径还原]城市交通路网 HUSTOJ2813

如图:求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;
}