题目

点击显/隐题目

pw特别喜欢蹭饭,所以他没事就去同学家拜访。他有三个朋友,feynman、pangcong和adrui,他们三个每人住在自己的屋子里。pw不仅蹭饭,每次辗转于三人的房屋时,还测出feynman家到pangcong家距离a米,feynman家到adrui家距离b米,pangcong家到adrui家距离c米。

pw不仅喜欢蹭饭,还特别能吃,他每天要吃n顿饭。现在他正在feynman家中,准备吃今天的第一顿饭。当然蹭饭也是要有原则的,不能连续在一个朋友家蹭饭。

Pw不仅能吃,还特别懒。他要吃n顿饭,还想要走的总路程最小,请你帮他算算最少要走多少米的路程。


第一行为数字n(1<=n<=100)表示要吃的饭的数目。
第二行为feynman家到pangcong家的距离a(1<=a<=100)。
第三行为feynman家到adrui家的距离b(1<=b<=100)。
第四行为pangcong家到adrui家的距离c(1<=c<=100)。


一个整数,表示需要走的最小的总路程。


3
2
3
1


3

题解

虽然是最短路问题,但是不需要使用DFS、BFS
可以自己画一画就可以发现,其实不管蹭多少顿饭,其实都是在最短的那条路上循环往返

所以只需要第一步走到最短的路上,然后直接用次数乘最短路的距离即可

代码

点击显/隐代码
蹭饭代码备份
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n;
int d[3];// 0->1 0->2 1->2
int dfs(int deep,int pos,int cost){
if(deep<=0)
return cost;
if(pos==0){
return min(dfs(deep-1,1,cost+d[0]),dfs(deep-1,2,cost+d[1]));
}else if(pos==1){
return min(dfs(deep-1,0,cost+d[0]),dfs(deep-1,2,cost+d[2]));
}else{
return min(dfs(deep-1,0,cost+d[1]),dfs(deep-1,1,cost+d[2]));
}
return -1;
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d%d%d",&n,&d[0],&d[1],&d[2]);
int ans;
if(n>1){
ans = dfs(1,0,0);
ans += (n-2)*min(d[0],min(d[1],d[2]));
}else{
ans = dfs(n-1,0,0);
}
printf("%d\n",ans);
return 0;
}