优先队列
优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认按元素值由大到小排序，可以重载“<”操作符来重新定义比较规则，和普通队列不同的是，队首元素是q.top()。
题目
在育英，大家最头疼的事情就是晨跑了，因为每天早上大家都要被迫从温暖的被窝爬起来去晨跑令人非常不爽。
育英的晨跑是使用一款APP来规定晨跑路线，我们可以把育英校园看作一个n * m的二维矩阵。LZY的起点在左上角（0，0），而APP规定的终点为右下角（n - 1,m - 1) 。
LZY跑到每个点的用时都不一样，现在LZY为了偷懒，想找一条耗时最短的捷径，你能帮帮他吗？
输入格式
测试样例由多组测试数据组成。每组测试数据第一行输入两个正整数n, m（1 <= n,m <= 100）
接下来输入n*m个数字，每个数字不超过500
输出
输出LZY从起点跑到终点的最短用时
输入样例
输出样例
8
代码
利用排序规则，让时间更短的路径出队顺序，提高效率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<bits/stdc++.h>
using namespace std;
int n,m,k,mixn;
int vis[110][110];
int Map[110][110];
int dir[4][2]={-1,0,1,0,0,-1,0,1};
struct fun{
int x,y;
int t;
friend bool operator<(fun a,fun b){
return a.t>b.t;
}
}great;
void bfs(){
priority_queue<fun> q;
great.x=0;
great.y=0;
great.t=Map[0][0];
vis[0][0]=1;
q.push(great);
mixn=0x7fffffff;
while(q.size()){
fun num=q.top();
q.pop();
if(num.x==n-1&&num.y==m-1){
mixn=num.t;
}
for(int i=0;i<4;i++){
int xx=num.x+dir[i][0];
int yy=num.y+dir[i][1];
if(xx<0||xx>=n||yy<0||yy>=m||num.t+Map[xx][yy]>mixn){
continue;
}
if(vis[xx][yy]==0){
vis[xx][yy]=1;
great.x=xx;
great.y=yy;
great.t=num.t+Map[xx][yy];
q.push(great);
}
}
}
}
int main(){
while(scanf("%d %d",&n,&m)!=EOF){
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&Map[i][j]);
}
}
bfs();
printf("%d\n",mixn);
}
return 0;
}
|