中山蚂蚁网站开发,常用的seo查询工具有哪些,十大耐玩手机单机游戏,怎么查一个网站的备案信息乌拉乌拉国有n个城市和m条道路#xff0c;城市编号为1∼n。由于乌拉乌拉国每一个城市都在创城#xff08;创建文明城市#xff09;#xff0c;因此#xff0c;城市之间的道路通行施行道路交通管制#xff1a; 已知从城市ui到城市vi的道路#xff0c;需要时间ti。… 乌拉乌拉国有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[i1]][0] tle[gl[i1]][gl[i]][0] now;now mp[gl[i]][gl[i1]] - 1;tle[gl[i]][gl[i1]][1] tle[gl[i1]][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}); } 总代码
#includebits/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 pairint,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_queuepii,vectorpii,greaterpii 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[i1]][0] tle[gl[i1]][gl[i]][0] now;now mp[gl[i]][gl[i1]] - 1;tle[gl[i]][gl[i1]][1] tle[gl[i1]][gl[i]][1] now;now ;}bfs(a,b,k);
}
