首次接触到优先队列是在http://acm.hdu.edu.cn/showproblem.php?pid=1242
题目意思：在一张图中，有多个朋友要去营救一个公主，其中'.'代表此条路可以走，需时间为1，'r'代表公主的朋友，'x'代表敌人，走这条路值时间需加1，'#'代表此条路不可走，问公主获救最小需要多少时间。
这道题目需要注意的地方是朋友是多个的，而公主只有一个，所以不能把朋友的位置当做起点，若如此，很多路径都会重复，必然超时。所以把公主的位置当做起点，当第一次找到某个朋友的时候用的时间即是最短时间。此时需要用到BFS，而碰到'x'和'.'所需要用到的时间是不一致的，这里优先队列变起到很明显的作用。
首先，优先队列的定义：每次从队列中取出的是具有最高优先权的元素。
其次，优先队列的应用很灵活，可以和其他算法很巧妙地结合，这得靠自己分析咯。
贴下这道题目代码：
#include<iostream>#include<queue>using namespace std;#define MAXN 205char map[MAXN][MAXN];int N,M,starti,startj;int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};struct love{ int x,y; int time; friend bool operator<(love a,love b){ return a.time>b.time; }//按权值从小到大排
};int BFS(int nowi,int nowj,int step){ priority_queue <love> Q; love first,next; first.x=nowi; first.y=nowj; first.time=step; Q.push(first); int fx,fy; while(!Q.empty()){ first=Q.top(); Q.pop(); for(int i=0;i<4;i++){ fx=dir[i][0]+first.x; fy=dir[i][1]+first.y; if(fx>=0&&fx<N&&fy>=0&&fy<M&&map[fx][fy]!='#'){ if(map[fx][fy]=='r'){ return first.time+1; } else if(map[fx][fy]=='.'){ next.time=first.time+1; } else if(map[fx][fy]=='x'){ next.time=first.time+2; } next.x=fx; next.y=fy; map[next.x][next.y]='#'; Q.push(next); } } } return -1;}int main(){ int i,j; while(cin>>N>>M) { for(i=0;i<N;i++){ for(j=0;j<M;j++){ cin>>map[i][j]; if(map[i][j]=='a'){ starti=i; startj=j; } } } int ans=BFS(starti,startj,0); if(ans==-1) printf("Poor ANGEL has to stay in the prison all his life./n" ); else printf("%d/n",ans); }}
