有域名一定要买空间做网站,上海国外网站建设,114黄页企业名录在哪里买,福州市建设厅网站蓝桥杯第十三届蓝桥杯大赛软件赛决赛C/C 研究生组之交通信号
题目链接[0交通信号 - 蓝桥云课 (lanqiao.cn)]
本题的思路十分简单#xff0c;先看题意#xff0c;是由n个节点#xff0c;m条边的有向图#xff0c;红绿灯的顺序为绿黄红黄#xff0c;在最开始时候为绿灯 研究生组之交通信号
题目链接[0交通信号 - 蓝桥云课 (lanqiao.cn)]
本题的思路十分简单先看题意是由n个节点m条边的有向图红绿灯的顺序为绿黄红黄在最开始时候为绿灯绿灯时可以通过这条边黄灯时不可以走红灯时则可以反方向走。每次往哪儿走就在于到达这个边的一瞬间看此时亮的是什么颜色的灯。
使用小顶堆来存储花费的时间每次花费最少的时间是在最上面在对图初始化时候分为正方向可以走的以及反向走的由于该图是个有向图因而要进行这样的初始化。然后就可以模拟这个过程来取得最短的时间可以参考一下代码来进行理解。
代码如下:
#include bits/stdc.h
using namespace std;
using ll long long;
const int N 1e5 10;
struct edge{int v;int g;int r;int y;
};
struct dis{ll d;int u;bool operator (dis d1) const{return d1.dd;} //自定义比较函数
};
int n, m, s, t;
vectoredge zheng[N], fan[N];
int main()
{priority_queuedis q; //小顶堆cinnmst;for(int i 1; i m; i){int u,v,g,r,d;scanf(%d%d%d%d%d, u, v, g, r, d);zheng[u].push_back({v,g,r,d});fan[v].push_back({u, g, r, d});}q.push({0, s});vectorll f(n1, LONG_MAX);//初始化时间为最长f[s]0;//起始顶点设置为0while(q.size()){auto[times,node] q.top();q.pop();for(auto e:zheng[node]) //需要绿灯的时候才可以走{ll tempf[node]%(1ll*e.ge.y1ll*e.re.y); //*1.ll是为了让其保持long long的数据范围if(tempe.g) //此时正处于绿灯{if(f[e.v]f[node]e.y){f[e.v] f[node]e.y; //将该节点的值修改q.push({f[e.v],e.v});}}else{if(f[e.v]f[node]e.y1ll*e.ge.y1ll*e.re.y-temp){f[e.v]f[node]e.y1ll*e.ge.y1ll*e.re.y-temp;q.push({f[e.v],e.v});}}}for(auto e:fan[node]) //此时属于反方向走只有红灯的时候可以经过{ll tempf[node]%(1ll*e.ge.y1ll*e.re.y);if(temp1ll*e.ge.ytemp1ll*e.ge.ye.r)//此时正处于红灯{if(f[e.v]f[node]e.y){f[e.v]f[node]e.y;q.push({f[e.v],e.v});}}else if(temp1ll*e.ge.y){if(f[e.v]f[node]1ll*e.ye.ge.y-temp){f[e.v]f[node]e.ye.ge.y-temp;q.push({f[e.v],e.v});}}else{if(f[e.v]f[node]1ll*e.ye.ge.ye.re.y-tempe.ge.y){f[e.v]f[node]e.ye.ge.ye.re.y-tempe.ge.y;q.push({f[e.v],e.v});}}}}if(f[t] LONG_LONG_MAX / 2){ cout-1;}else {coutf[t];}return 0;
}
