“蔚来杯“2022牛客暑期多校训练营3 J.Journey 0-1最短路

J.Journey 题目分析

给定一个城市有若干十字路口，右转需要等红灯，直行、左转和掉头都需要，求起点到终点最少等几次红灯。

可以将每条路径视为点，十字路口处分情况连边，边权赋为 0 , 1 0,1 0,1，转化为 0 − 1 0-1 0−1最短路问题，然后直接跑 d i j k s t r a dijkstra dijkstra即可。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 4e6 + 10;

#define pii pair
#define mkp make_pair
#define fir first
#define sec second

int n = 0, cnt = 0;
int s1, s2, t1, t2;
vector g[N];
int dis[N];

struct node{
    int fa, to, res, id;
    const bool operator x.res; }
};

priority_queue pq;

void dijkstra(){
    for(int i = 0; i  n;
    memset(dis, -1, sizeof(dis));
    for(int i = 1; i  v;
            g[i].emplace_back(mkp(v, ++cnt));
        }
    }
    cin >> s1 >> s2 >> t1 >> t2;
    dijkstra();
    for(int i = 0; i