题意

第 $i$ 个点到第 $j$ 个点要支付 $a_{i,j}$ 个费用。求从第 1 个点走到第 $n$ 个点的最短费用

思路

依照图片，可以发现这是从终点往起点找的，那我们也这样找。

那这样就和数字金字塔一样好找了！

由于第 $i$ 个城市只能到大于 $i$ 的城市，所以内层循环从 $i + 1$ 开始遍历

注意：

• 由于要求最小值，所以要初始化数组
• 要记得记录路线

代码

#include <bits/stdc++.h>
using namespace std;
int a[25],w[25][25],l[25];
int main(int argc, char **argv){
	memset(a,0x7f,sizeof(a));
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= n;j++){
			cin >> w[i][j];	// i 到 j 的费用
		}
	}
	a[n] = 0;	// 边界
	for (int i = n - 1;i > 0;i--){	// 从终点往起点遍历
		for (int j = i + 1;j <= n;j++){	// 第 i 个点能去的地方
			// 如果 i 可以去 j，且费用更小，那就更新路线
			if (w[i][j] && a[i] > a[j] + w[i][j]){
				a[i] = a[j] + w[i][j];
				l[i] = j;	// 记录路线
			}
		}
	}
	printf("minlong=%d\n",a[1]);	// 起点记录最短费用
	int idx = 1;
	while (idx != 0){	// 输出路线，终点指向 0
		printf("%d ",idx);
		idx = l[idx];	// idx 指向的点
	}
	return 0;
}

参考与鸣谢

本题解参考了《信息学奥赛一本通》上【例 9.5】的代码

正向递推的版本，可能更好理解

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int n,w[101][101],dp[101],jl[100];//dp数组用于存到达第i个节点所用的最短距离 
stack <int> q;
int main ()
{
	cin >> n ;
    memset(dp,0x7f,sizeof(dp));			//初始化为无限 
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cin >> w[i][j];
		}
	}
	dp[1]=0;							//dp边界，到达第一个节点需要的路程为0 
	for (int i=1;i<n;i++){				//遍历每个节点 
		for (int j=1;j<=n;j++){
			if (w[i][j] && dp[i]+w[i][j]<dp[j]){	//如果有路，且当前距离+这条路的距离<下一节点最短距离，那么更新 
				dp[j]=dp[i]+w[i][j];
				jl[j]=i;							//表示第j个节点从第jl[j]来 
			} 
		}
	}
	cout << "minlong=" << dp[n] << endl;
	q.push(n);										//重点入栈 
	while(q.top()!=1){
		q.push(jl[q.top()]);						//不断寻找上一个节点并入栈 
	}
	while(!q.empty())
	{
		cout << q.top() << " ";						//反向输出 
		q.pop();
	}
	return 0;										//结束 
 }

给我点茶品的人没有几把

#include<iostream>
#include<stack>
using namespace std;
int main()
{
	int n;
	cin>>n;
	long long f[n+1]={};
	fill(&f[1],&f[n+1],0x7fffffff);
	f[1]=0;
	int r[n+1]={};
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int a;
			cin>>a;
			if(a&&f[j]>f[i]+a)
			{
				f[j]=f[i]+a;
				r[j]=i;
			}
		}
	}
	r[1]=0;
	cout<<"minlong="<<f[n]<<"\n";
	stack<int> s;
	int i=n;
	while(i)
	{
		s.push(i);
		i=r[i];
	}
	while(!s.empty())
	{
		cout<<s.top()<<" ";
		s.pop();
	}
}

AC代码(From 一本通)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//long long 太长了,缩写为ll; 
int main(){
	ll n,i,j,x,f[100],c[100],a[100][100];//a即题目要求输入的数组 ,设为long long可以解决大部分的溢出问题 
	memset(a,0,sizeof(a));
	memset(c,0,sizeof(c));//初始化数组
	cin>>n;//输入城市的数量
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			cin>>a[i][j];//循环输入a,即城市交通图 
	for(i=1;i<=n;i++)
		f[i]=114514;//默认两市之间距离，一本通上是10^6，因为有这个循环初始化，所以一开始没有必要给F初始化 
	f[n]=0;
	for(i=n-1;i>=1;i--)//逆推
		for(x=i+1;x<=n;x++)
			if((a[i][x]>0)&&(f[x]!=114514)&&(f[i]>a[i][x]+f[x]))//f[x]=114514表示x到终点城市不通，不列入计算范围
			//a[i][x]>0说明城市i与x通路 
			{
				f[i]=a[i][x]+f[x];//城市i最短路径值为上一城市x的最短路径值与两城之间距离之和 
				c[i]=x;//存储路径节点 
			} 
	cout<<"minlong="<<f[1]<<endl;//整条线的最短路径即为f[1](相当于v10至v1的最短路径)
	x=1;
	while(x!=0){
		cout<<x<<' ';//输出路径节点值
		x=c[x];//过渡到下一个节点 
	} 
	cout<<endl; 
	return 0;
}

题意

return;

思路

参照hmz的

代码

#include<iostream>
#include<queue>
#define int long long
#define Mojang_AB_xiang_qi 100
#define Mojang_AB_ni_de_mc_da_guai_ji 100
using namespace std;
int n;
int a[Mojang_AB_ni_de_mc_da_guai_ji][Mojang_AB_xiang_qi];
int dp[114514];
int road[114514];
signed main()
{
	fill(dp,dp+114514,0x114514f);
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>a[i][j];
		}
	}
	dp[n-1]=0;
	for(int i=n-2;i>-1;i--)
	{
		for(int j=i;j<n;j++)
		{
			if(a[i][j] && dp[i]>dp[j]+a[i][j])
			{
				dp[i]=dp[j]+a[i][j];
				road[i]=j+1;
			}
		}
	}
	cout<<"minlong="<<dp[0]<<endl;
	int id=1;
	while(id!=0)
	{
		cout<<id<<" ";
		id=road[id-1];
	}
	return 0;
}

广告

象棋是中国文化的特色之一,受到各年龄段的人们喜爱,不仅​玩法独特​,还极考验智慧

《中国象棋(pwm制作)》是由Mօjang AB 公司开发的一款象棋游戏,不仅可以​双人玩​,还可以与好友联机

点我进入《中国象棋(pwm制作)》主页