来源：牛客网
题目描述
自攻打过太原县城以后，李云龙这意大利炮就使用的越发的顺手了，指哪打哪也是绝不含糊，于是小野队长开始疯狂打击独立团炮兵营，为了锻炼士兵移动意大利炮的能力，李团长开始给炮兵营进行特训，众(wo)所(xia)周(bian)知(de)，意大利炮可由炮管，车轮，炮弹三部分组成，现在李团长在洋村设立阵地，分别把炮管，车轮，炮弹放在三个不同的地方，每一部分的重量不同，所以运输的速度也不相同。团长说：你谁有能耐最快把这意大利炮组装好然后运到我面前，老子就赏他半斤地瓜烧，和尚听了乐坏了，但是他不知道怎么才能使时间最快，你能帮帮他么？
零件只要拿起，就不能放下，所以说不存在在a点拿起，b点放下再去取别的零件一说。默认和尚1秒走一个单位距离，并且只能向上下左右四个方向走，假设和尚现在拿着炮管，那么他每走一单位距离则需要（t1 + 1）秒，如果再拿上车轮，那么他现在每走一步则需要（t1 + t2+1）秒的时间，以此类推。点可以重复经过，路过有零件的点时，可以选择拿或者不拿。
输入描述:
第一行给定两个整数n, m代表地图大小，(1<=n, m <= 100)；接下来n行每行有m个由‘#’和‘.’组成的字符，’#’代表墙，’.’代表路，和尚功夫高，可以自己或者带着零件*(不论墙多厚)，但是组装好意大利炮之后就必需得走路了。地图画好之后，接下来一行有10个整数sx,sy,x1, y1, x2, y2, x3, y3, ex, ed（都小于100）代表五个点，分别是起始点，炮管的位置，车轮的位置，炮弹的位置，李团长的位置(终点)， 五个点保证不同。最后一行三个整数t1, t2, t3，（都大于等于1，小于100），分别代表炮管，车轮，炮弹每走一单位距离需要的时间。题目保证数据合法。
输出描述:
输出一个整数并换行，代表和尚完成任务所需要的最短时间。题目保证有解。
题解：
起点和终点确定，中间三点的顺序有六种情况，遍历即可。
#include<bits/stdc++.h>using namespace std;int n,m,sx,sy,ex,ey,x1,y11,x2,y2,x3,y3,t1,t2,t3;int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};bool mp[101][101];char t[101][101];struct node{ int x,y,step;};queue<node>P;int bfs(int tx,int ty,int rx,int ry,int v){ while(!P.empty())P.pop(); memset(mp,0,sizeof(mp)); node r;r.x=tx,r.y=ty,r.step=0; P.push(r);mp[r.x][r.y]=1; while(!P.empty()) { r=P.front();P.pop(); if(r.x==rx&&r.y==ry) return r.step; for(int i=0;i<4;i++) { int xx=r.x+d[i][0],yy=r.y+d[i][1]; if(xx<0||xx>=n||yy<0||yy>=m)continue; if((t[xx][yy]!='#'||v!=(t1+t2+t3+1))&&!mp[xx][yy]) { mp[xx][yy]=1; node e;e.x=xx;e.y=yy;e.step=r.step+v; P.push(e); } } } return 1e9;}int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",&t[i]); scanf("%d%d%d%d%d%d%d%d%d%d%d%d%d",&sx,&sy,&x1,&y11,&x2,&y2,&x3,&y3,&ex,&ey,&t1,&t2,&t3); sx--,sy--,x1--,y11--,x2--,y2--,x3--,y3--,ex--,ey--; int ans=1e9; ans=min(ans,bfs(sx,sy,x1,y11,1)+bfs(x1,y11,x2,y2,t1+1)+bfs(x2,y2,x3,y3,t1+t2+1)+bfs(x3,y3,ex,ey,t1+t2+t3+1)); ans=min(ans,bfs(sx,sy,x1,y11,1)+bfs(x1,y11,x3,y3,t1+1)+bfs(x3,y3,x2,y2,t1+t3+1)+bfs(x2,y2,ex,ey,t1+t2+t3+1)); ans=min(ans,bfs(sx,sy,x2,y2,1)+bfs(x2,y2,x1,y11,t2+1)+bfs(x1,y11,x3,y3,t1+t2+1)+bfs(x3,y3,ex,ey,t1+t2+t3+1)); ans=min(ans,bfs(sx,sy,x2,y2,1)+bfs(x2,y2,x3,y3,t2+1)+bfs(x3,y3,x1,y11,t2+t3+1)+bfs(x1,y11,ex,ey,t1+t2+t3+1)); ans=min(ans,bfs(sx,sy,x3,y3,1)+bfs(x3,y3,x1,y11,t3+1)+bfs(x1,y11,x2,y2,t1+t3+1)+bfs(x2,y2,ex,ey,t1+t2+t3+1)); ans=min(ans,bfs(sx,sy,x3,y3,1)+bfs(x3,y3,x2,y2,t3+1)+bfs(x2,y2,x1,y11,t2+t3+1)+bfs(x1,y11,ex,ey,t1+t2+t3+1)); printf("%d\n",ans); return 0;}