题目

{% fold 点击显/隐题目 %}

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
{% endfold %}

题解

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

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

代码

{% fold 点击显/隐代码 %}```cpp 蹭饭 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
#include
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;

}

{% endfold %}