自动搬运

查看原文

来自洛谷，原作者为

	DicaprioD 待夕阳生暮意

搬运于2025-08-24 22:27:32，当前版本为作者最后更新于2024-04-26 17:26:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

堆优化版 Dijkstra

这道题是刚学完最短路刷题时遇到了，感觉是一道板子题，只需要根据题意多加一些东西就可以了，并不难。

分析

首先，只需要把十字路口理解为点，路理解为边，时间作为权值，即可转化为一道较为传统的最短路问题。

再看一下数据范围，可以判断此题是一个稠密图，用邻接矩阵来存储十分方便。

然后，读题发现边的权值绝对不是负数，那么我们就可以来打一手 Dijkstra 了，最后再看时空限制，打一个堆优化更为稳妥。

但这道题不是纯板子，题目给到了我们一些限制，在 Luka 按照我们规划好的最短路前进时，可能会遇到 T 先生的干扰，如果赶到一个点时，恰好 T 先生也在这，那 Luka 只能等待，所以现在摆在我们面前的问题是：

• Luka 会在哪个点遇到 T 先生？
• Luka 会在那个点等多长时间？

相对应的我们给出如下解决措施：

• 预处理出 T 先生会经过的点，以及从 $x$ 到 $y$ 的时间，在跑 Dijkstra 时特判即可。
• 思考一下，如果 Luka 在从 $x$ 到 $y$ 路径上遇到了 T 先生，那么他花费的时间不仅是自己通过所用时间，还有等待 T 先生通过的时间，也就是说，总共所用时间是原本的双倍，需要注意的是，T 先生在 Luka 到达前就可能在这条路上走了一段时间，需要减去这段时间。
• 以上操作，详解看代码。

有了这些准备之后，就可以套模板了。 代码里可能还会有一些小细节。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
typedef pair<int,int> PII;
int n,m;
int b,e,k,g;
int mp[N][N];//存图
int TT[N][N],past[N];//上面有解释
int d[N];
bool st[N];
//这个自定义函数来判断一下,y先生是否在这条路上以及Luka通过需要的时间
int ff(int x,int y){
  //这段代码几乎每篇题解都有，这里做一下详细的解释
	if(d[x]>=TT[x][y]&&d[x]<=TT[x][y]+mp[x][y]-1){//如果到达这条路时T先生正在这里游玩
		return TT[x][y]+mp[x][y]*2;//那么我们要在原本的等待时间上*2,因为Luka是在T先生走完这条路之后重新走一遍,相当于走了两遍.
   //至于为什么实在T先生的时间基础上操作,而不用d[x]+mp[x][y]*2,因为Luka到达时，T 先生可能已经在这条路上走了一会了.可以理解一下下面这个式子
   //return d[x]+mp[x][y]*2-(d[x]-TT[x][y])
    
	}
	else return d[x]+mp[x][y];
}
//下面是 Dijkstra 的模板
void Dijkstra(){
	memset(d,0x3f,sizeof d);
	d[b]=k;
	priority_queue<PII,vector<PII> ,greater<PII> > heap;
	heap.push(make_pair(k,b));
	while(heap.size()){
		auto t=heap.top();
		heap.pop();
		int ver=t.second;
		if(st[ver]) continue;
		st[ver]=1;
		for(int i=1;i<=n;i++){
			if(mp[ver][i]){
				int distance = ff(ver,i);
				if(distance<d[i]){
					d[i]=distance;
					heap.push(make_pair(distance , i));
				}
			}
		}
	}
}
int main(){
	cin>>n>>m;
	cin>>b>>e>>k>>g;
	for(int i=1;i<=g;i++){
		cin>>past[i];
	}
  //输入
	while(m--){
		int a,b,l;
		cin>>a>>b>>l;
		mp[a][b]=l;
		mp[b][a]=l;
	}
  //邻接矩阵存边
	int now=0;
	for(int i=1;i<g;i++){
		TT[past[i]][past[i+1]] = now;
		TT[past[i+1]][past[i]] = now;
		now += mp[past[i]][past[i+1]];
      //past 数组存放的是 T 先生经过的点
  //mp 数组是地图
  //TT[x][y] 表示 T 先生从 x 到 y 的时间 注意无向图双向存边
  //注意时间是在累加的 所以 now 的值在不断叠加
	}
	Dijkstra();
	cout<<d[e]-k;//注意减去初始时间
	return 0;
}

若有问题，欢迎大家指出。

完结撒花 ！