hdu2425答题报告

hdu2425解题报告

题意很明了，就是找起点到终点的最短用时，但是因为每种不同的地带，用时不同，那么这里可以用到优先队列，来处理总共用时，我们每次总是把用时最短的坐标点出队，访问四周，那么，就总能选择用时最短的去走，直到达到目的地：

上马：

0MS244K

#include<cstdio>#include<queue>using namespace std;#define MAX 22struct node{int x,y,time;//坐标，以及起点到此点的用时bool operator <(const node &N)const//用优先队列，按用时从小到大排序{return N.time<time;}}st;//开始点int R,C;//行列int endx,endy;//目标的坐标char map[MAX][MAX];int T[3];//对于三种不同地带的用时void Input(){int i;scanf("%d%d%d",&T[0],&T[1],&T[2]);for(i=0;i<R;i++,getchar())scanf("%s",map[i]);scanf("%d%d%d%d",&st.x,&st.y,&endx,&endy);st.time=0;}int vis[4][2]={{-1,0},{1,0},{0,1},{0,-1}};int bfs(){priority_queue<node>q;map[st.x][st.y]='@';//走过了的地方我们就标记为石头，不再走q.push(st);while(!q.empty()){node pre=q.top();q.pop();if(pre.x==endx && pre.y==endy){return pre.time;}for(int i=0;i<4;i++){node p;p.x=pre.x+vis[i][0];p.y=pre.y+vis[i][1];p.time=pre.time;if(p.x>=0 && p.y >= 0 && p.x < R && p.y < C && map[p.x][p.y]!='@')//对于地图中不是石头的地方访问{if(map[p.x][p.y]=='T')p.time+=T[2];//这里看看是哪一种地带，else if(map[p.x][p.y]=='.')p.time+=T[1];else if(map[p.x][p.y]=='#')p.time+=T[0];map[p.x][p.y]='@';q.push(p);}}}return -1;//走不到返回-1}int main(){int cas=1;while(~scanf("%d%d",&R,&C)){Input();printf("Case %d: %d\n",cas++,bfs());}return 0;}