题意

• 走迷宫，迷宫中有传送门，使用传送门需要花费三秒，求解从起点到终点的最短时间

思路

• 相较于传统搜索，出现的问题是对于一个点可能有多个到达时间，我们希望记录这多个时间中最短的时间
• 对于传送门，由于同一个点可能有多个传送门，所以不能使用点对点的映射，使用点对数组的映射，map<int,vector>
• 换言之，对于一个点的多个时间，我们处理完最短的就可以了，同时对于所有路径，我们总希望先处理当前时间最短的时间，故从维护队列变为维护优先队列，维护一个大顶堆，存储坐标和时间的pair
• 同时对于传统的vis数组，不再是只要走到就更新，而是时间最早的被处理后，更新vis
• 由于上一条，所以判断达到终点的最短时间也应当在终点第一次位于堆顶后，再进行输出
• 由于传送门可能位于起点，所以bfs的初始化除了将自己入队，还要将起点的传送终点也入队
• 由于传送的终点可能位于陷阱之中或是已经走过的地方，所以，每次在将传送终点入队前，需要先判断是否合法

注意

• 行列别读反
• 由于多组数据，vis，传送门，地图每次都需要初始化
• 对于将坐标转换为一个数这件事，0开始：n行m列的(x,y)=>xm+y，1开始：n行m列的(x,y)=>x(m+1)+y

AC代码

#include<bits/stdc++.h>
using namespace std;
char a[320][320];
int vis[320][320];
int n,m,q;
int d[4][2]={0,1,0,-1,1,0,-1,0};
map<int,vector<int>>dr;
struct cmp{
  bool operator()(pair<int,int> &a,pair<int,int> &b){
  	return a.second>b.second;
  }
};

int bfs(int s,int e){
  priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>q;
  q.push({s,0});
//	vis[s/m][s%m]=1;
  if(dr.find(s)!=dr.end()){
  	for(auto &j:dr[s]){
  		if(a[j/m][j%m]=='#'||vis[j/m][j%m]==1)continue;
  		q.push({j,3});
  	}
  }
  while(q.size()){
  	int x=q.top().first/m;
  	int y=q.top().first%m;
  	int step=q.top().second;
  	q.pop();
  	if(vis[x][y])continue;		
  	vis[x][y]=1;
  	if(x==e/m&&y==e%m) return step;

  	for(int i=0;i<4;i++){
  		int tx=x+d[i][0];
  		int ty=y+d[i][1];
  		if(tx<0||tx>=n||ty<0||ty>=m||a[tx][ty]=='#'||vis[tx][ty]==1)continue;
  		q.push({tx*m+ty,step+1});
  		if(dr.find(tx*m+ty)!=dr.end()){
  			for(auto &j:dr[tx*m+ty]){
  				if(a[j/m][j%m]=='#'||vis[j/m][j%m]==1)continue;
  				q.push({j,step+4});
  			}
  		}
  	}
  }
  return -1;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  while(cin>>n>>m>>q){
  	int start,en;
  	memset(a,'\0',sizeof(a));
  	memset(vis,0,sizeof(vis));
  	dr.clear();
  	for(int i=0;i<n;i++){
  		for(int j=0;j<m;j++){
  			cin>>a[i][j];
  			if(a[i][j]=='S') start=m*i+j;
  			if(a[i][j]=='T') en=m*i+j;
  		}
  	}
  	for(int i=0;i<q;i++){
  		int x1,y1,x2,y2;
  		cin>>x1>>y1>>x2>>y2;
  		dr[x1*m+y1].push_back(x2*m+y2);
  	}
  	cout<<bfs(start,en)<<'\n';
  }


  return 0;
}