这是一篇最后编辑于 8 年前 的文章，其内容可能与目前实际情况差异较大，请注意甄别
题目
{% 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）。
一个整数，表示需要走的最小的总路程。
题解
虽然是最短路问题,但是不需要使用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 %}