题解：P7192 [COCI2007-2008#6] GEORGE
堆优化版 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;
}若有问题，欢迎大家指出。
完结撒花 ！