PTA 道路管制

乌拉乌拉国有n个城市和m条道路，城市编号为1∼n。由于乌拉乌拉国每一个城市都在创城（创建文明城市），因此，城市之间的道路通行施行道路交通管制：
 已知从城市ui​到城市vi​的道路，需要时间ti​。但是一旦当道路管理员进入某条道路后，任何人在道路管理员未驶出该道路前不允许进入该道路。例如：道路管理员在第4时刻进入该道路，在路上需要花费3时，那么在第4∼6时刻不允许其他人进入改街道，只能第7时刻及其以后进入或者在第4时刻之前进入。
 现在，计算鸭知道，道路管理员从0时刻出发，依次经过g个城市，计算鸭从时刻k出发，从城市a前往城市b。请问，计算鸭最少需要多长时间。

输入格式:

输入的第一行给出两个整数n,m——表示城市的数量和道路的数量。

输入的第二行给出四个整数a,b,k,g——a,b分别表示计算鸭的初始城市和目的城市；k表示计算鸭出发时刻；g表示道路管理员需要经过的城市数量。

输入的第三行给出g个整数xi​——表示道路管理员需要经过的城市编号。

接下来m行，每行3个整数ui​,vi​,ti​——表示从ui​至vi​需要用时ti​

2≤n≤103

2≤m≤104

1≤a,b,ui​,vi​≤n

0≤k,g≤103

1≤ti​≤103

输出格式:

输出一个整数——表示计算鸭从a城市到b城市的最短用时。

输入样例:

6 5
1 6 20 4
5 3 2 4
1 2 2
2 3 8
2 4 3
3 6 10
3 5 15 

输出样例:

21

输入样例:

8 9
1 5 5 5
1 2 3 4 5
1 2 8
2 7 4
2 3 10
6 7 40
3 6 5
6 8 3
4 8 4
4 5 5
3 4 23 

输出样例:

40

思路： 

定义一个mp[N][N]数组记录每条道路的长度；

    for(int i = 1 ; i <= m ; i ++){
		ll u , v , w;
		cin >> u >> v >> w;
		add(u,v,w) , add(v,u,w);
		mp[u][v] = mp[v][u] = w;
	}

一个tle[N][N][2]数组记录道路的禁止进入的开始和结束时间，now为当前的时间。

比如3->5的花费是15，那么禁行时间为0->14，接下来3->2是8，禁行时间为15->22；

    for(int i = 0 ; i < g - 1; i ++){
		tle[gl[i]][gl[i+1]][0] = tle[gl[i+1]][gl[i]][0] = now;
		now += mp[gl[i]][gl[i+1]] - 1;
		tle[gl[i]][gl[i+1]][1] = tle[gl[i+1]][gl[i]][1] = now;
		now ++ ;
	}

 记录鸭要从k时压入队列进行做短路。

如果当前点的时间花费在不能走当前想走的道路的禁行时间内，那么只能在禁行时间后开始走。

若不在禁行时间内，则直接进行普通最短路。

    if(dist[t] >= tle[t][x][0] && dist[t] <= tle[t][x][1]){
	    if(dist[x] <= tle[t][x][1] + 1 + w[i])continue;
	    dist[x] = tle[t][x][1] + 1 + w[i];
	    q.push({dist[x],x});
	}else{
	    if(dist[x] <= dist[t] + w[i])continue  ;
		dist[x] = dist[t] + w[i];
		q.push({dist[x],x}); 
	}

 总代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n , m , T ;
const int N = 1005 , M = 20005;
int e[M] , ne[M] , w[M] , dist[N] , h[N] , idx;
bool st[N];
void add(int a,int b,int c){
	ne[idx] = h[a] , e[idx] = b , w[idx] = c , h[a] = idx ++;
}
#define pii pair<int,int>
ll tle[N][N][2];
void bfs(int a,int b,int k){
	memset(dist,0x3f,sizeof dist);
	memset(st,0,sizeof st);
	priority_queue<pii,vector<pii>,greater<pii> >q;
	dist[a] = k;
	q.push({dist[a],a});
	while(!q.empty()){
		auto t = q.top().second;
		q.pop();
		if(st[t])continue ;st[t] = 1;
		for(int i = h[t] ; ~ i ; i = ne[i]){
			int x = e[i];
			if(dist[t] >= tle[t][x][0] && dist[t] <= tle[t][x][1]){
				if(dist[x] <= tle[t][x][1] + 1 + w[i])continue;
				dist[x] = tle[t][x][1] + 1 + w[i];
				q.push({dist[x],x});
			}else{
				if(dist[x] <= dist[t] + w[i])continue  ;
				dist[x] = dist[t] + w[i];
				q.push({dist[x],x}); 
			}
		}
	}
	cout << dist[b] - k << endl;
}
ll mp[N][N] , gl[N];
int main(){
	idx = 0;
	memset(h , -1,sizeof h);
	cin >> n >> m;
	ll a , b , k , g;
	cin >> a >> b >> k >> g;
	for(int i = 0 ; i < g ; i ++){
		cin >> gl[i];
	}
	ll cnt = 0 , now = 0;
	for(int i = 1 ; i <= m ; i ++){
		ll u , v , w;
		cin >> u >> v >> w;
		add(u,v,w) , add(v,u,w);
		mp[u][v] = mp[v][u] = w;
	}
	for(int i = 0 ; i < g - 1; i ++){
		tle[gl[i]][gl[i+1]][0] = tle[gl[i+1]][gl[i]][0] = now;
		now += mp[gl[i]][gl[i+1]] - 1;
		tle[gl[i]][gl[i+1]][1] = tle[gl[i+1]][gl[i]][1] = now;
		now ++ ;
	}
	bfs(a,b,k);
}