本文主要是介绍ACM/ICPC 2018亚洲区预选赛北京赛站网络赛 Saving Tang Monk II —— dijkstra+优先队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Cheng’en during the Ming Dynasty. In this novel, Monkey King Sun Wukong, pig Zhu Bajie and Sha Wujing, escorted Tang Monk to India to get sacred Buddhism texts.
During the journey, Tang Monk was often captured by demons. Most of demons wanted to eat Tang Monk to achieve immortality, but some female demons just wanted to marry him because he was handsome. So, fighting demons and saving Monk Tang is the major job for Sun Wukong to do.
Once, Tang Monk was captured by the demon White Bones. White Bones lived in a palace and she cuffed Tang Monk in a room. Sun Wukong managed to get into the palace, and he wanted to reach Tang Monk and rescue him.
The palace can be described as a matrix of characters. Different characters stand for different rooms as below:
‘S’ : The original position of Sun Wukong
‘T’ : The location of Tang Monk
‘.’ : An empty room
‘#’ : A deadly gas room.
‘B’ : A room with unlimited number of oxygen bottles. Every time Sun Wukong entered a ‘B’ room from other rooms, he would get an oxygen bottle. But staying there would not get Sun Wukong more oxygen bottles. Sun Wukong could carry at most 5 oxygen bottles at the same time.
‘P’ : A room with unlimited number of speed-up pills. Every time Sun Wukong entered a ‘P’ room from other rooms, he would get a speed-up pill. But staying there would not get Sun Wukong more speed-up pills. Sun Wukong could bring unlimited number of speed-up pills with him.
Sun Wukong could move in the palace. For each move, Sun Wukong might go to the adjacent rooms in 4 directions(north, west,south and east). But Sun Wukong couldn’t get into a ‘#’ room(deadly gas room) without an oxygen bottle. Entering a ‘#’ room each time would cost Sun Wukong one oxygen bottle.
Each move took Sun Wukong one minute. But if Sun Wukong ate a speed-up pill, he could make next move without spending any time. In other words, each speed-up pill could save Sun Wukong one minute. And if Sun Wukong went into a ‘#’ room, he had to stay there for one extra minute to recover his health.
Since Sun Wukong was an impatient monkey, he wanted to save Tang Monk as soon as possible. Please figure out the minimum time Sun Wukong needed to reach Tang Monk.
输入
There are no more than 25 test cases.
For each case, the first line includes two integers N and M(0 < N,M ≤ 100), meaning that the palace is a N × M matrix.
Then the N×M matrix follows.
The input ends with N = 0 and M = 0.
输出
For each test case, print the minimum time (in minute) Sun Wukong needed to save Tang Monk. If it’s impossible for Sun Wukong to complete the mission, print -1
样例输入
2 2
S#
#T
2 5
SB###
##P#T
4 7
SP…
P#…
…#
B…##T
0 0
样例输出
-1
8
11
题意：
从s到t，走过一个‘.’，‘B’,‘P’需要一个单位时间，走过一个’#'需要两个时间，走过b时可以获得一个氧气瓶，站在那里不会获得更多，但是来回走可以获得多个氧气瓶，走过一个p可以不花时间的往任意方向走一格，走过一个‘#’需要两个单位的时间并且消耗掉一个氧气瓶。问你从s到t的最短时间是多少，如果不可能输出-1.
题解：
和南京的一道题目很像：https://blog.csdn.net/tianyizhicheng/article/details/82313603
也是用优先队列，写一个dp方程，再稍微判断一下情况就好了，这个是队友的代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,m,k,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
ll ans;
char mp[105][105];
struct Node
{int dis,x,y,num;Node(){}Node(int dis,int x,int y,int num) : dis(dis),x(x),y(y),num(num){}bool operator < (const Node& rhs) const{if(dis!=rhs.dis)return dis > rhs.dis;else return num>rhs.num;}
};
ll dis[105][105][8];
bool vis[105][105][8];
int ck(int x,int y){if(x<1||x>n||y<1||y>m) return 0;return 1;
}
void Dijkstra(int stx,int sty,int enx,int eny){priority_queue<Node> Q;while(!Q.empty()) Q.pop();Q.push(Node(0,stx,sty,0));dis[stx][sty][0]=0;while(!Q.empty()){Node u = Q.top(); Q.pop();if(vis[u.x][u.y][u.num]) continue;vis[u.x][u.y][u.num] = 1;//printf("x=%d y=%d dis=%d num=%d\n",u.x,u.y,u.dis,u.num);for(int i=0;i<4;i++){int dx=u.x+dir[i][0],dy=u.y+dir[i][1];if(!ck(dx,dy)) continue;if(mp[dx][dy]=='#'){if(u.num==0) continue;if(u.dis+2< dis[dx][dy][u.num-1]){dis[dx][dy][u.num-1]=u.dis+2;Q.push(Node(u.dis+2,dx,dy,u.num-1));}}if(mp[dx][dy]=='.'||mp[dx][dy]=='S'||mp[dx][dy]=='T'){if(u.dis+1< dis[dx][dy][u.num]){dis[dx][dy][u.num]=u.dis+1;Q.push(Node(u.dis+1,dx,dy,u.num));}}if(mp[dx][dy]=='P'){if(u.dis<dis[dx][dy][u.num]){dis[dx][dy][u.num]=u.dis;Q.push(Node(u.dis,dx,dy,u.num));}}if(mp[dx][dy]=='B'){if(u.dis+1<dis[dx][dy][u.num+1]){dis[dx][dy][u.num+1]=u.dis+1;Q.push(Node(u.dis+1,dx,dy,u.num+1));}}}}
}
int main(){//printf("%lld\n",INF);while(~scanf("%d%d",&n,&m)){if(n==0&&m==0) break;int stx,sty,enx,eny;for(int i=1;i<=n;i++){scanf("%s",mp[i]+1);for(int j=1;j<=m;j++){for(int k=0;k<=5;k++)vis[i][j][k]=0,dis[i][j][k]=inf;if(mp[i][j]=='S')stx=i,sty=j;if(mp[i][j]=='T')enx=i,eny=j;}}ans=inf;Dijkstra(stx,sty,enx,eny);for(int i=0;i<=5;i++){ans=min(ans,dis[enx][eny][i]);}if(ans==inf) printf("-1\n");else printf("%lld\n",ans);}return 0;
}这篇关于ACM/ICPC 2018亚洲区预选赛北京赛站网络赛 Saving Tang Monk II —— dijkstra+优先队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
