蓝桥杯第十三届蓝桥杯大赛软件赛决赛CC++ 研究生组之交通信号

蓝桥杯第十三届蓝桥杯大赛软件赛决赛C/C++ 研究生组之交通信号

题目链接[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.d<d;} //自定义比较函数
};
int n, m, s, t;
vector<edge> zheng[N], fan[N];
int main()
{
  priority_queue<dis> q;  //小顶堆
  cin>>n>>m>>s>>t;
  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});
  vector<ll> f(n+1, LONG_MAX);//初始化时间为最长
  f[s]=0;//起始顶点设置为0
  while(q.size())
  {
      auto[times,node] = q.top();
      q.pop();
      for(auto &e:zheng[node]) //需要绿灯的时候才可以走
      {
          ll temp=f[node]%(1ll*e.g+e.y+1ll*e.r+e.y); //*1.ll是为了让其保持long long的数据范围
          if(temp<e.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.y+1ll*e.g+e.y+1ll*e.r+e.y-temp)
              {
                  f[e.v]=f[node]+e.y+1ll*e.g+e.y+1ll*e.r+e.y-temp;
                  q.push({f[e.v],e.v});
              }
          }
      }
      for(auto &e:fan[node]) //此时属于反方向走，只有红灯的时候可以经过
      {
          ll temp=f[node]%(1ll*e.g+e.y+1ll*e.r+e.y);
          if(temp>=1ll*e.g+e.y&&temp<=1ll*e.g+e.y+e.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(temp<1ll*e.g+e.y)
          {
              if(f[e.v]>f[node]+1ll*e.y+e.g+e.y-temp)
              {
                  f[e.v]=f[node]+e.y+e.g+e.y-temp;
                  q.push({f[e.v],e.v});
              }
          }
          else
          {
              if(f[e.v]>f[node]+1ll*e.y+e.g+e.y+e.r+e.y-temp+e.g+e.y)
              {
                  f[e.v]=f[node]+e.y+e.g+e.y+e.r+e.y-temp+e.g+e.y;
                  q.push({f[e.v],e.v});
              }
          }
      }


  }
  if(f[t] == LONG_LONG_MAX / 2){ cout<<-1;}
  else {cout<<f[t];}
  return 0;
}