"Wei Lai Cup" 2022 Niuke summer multi school training camp 3 j.journey 0-1 shortest path

J.Journey

Topic analysis

There are several intersections in a given city , You need to wait for the red light to turn right , Go straight 、 Both left turns and U-turns are required , Please wait for the red light at least several times from the beginning to the end .

You can think of each path as a point , The situation of intersection disposal is even , Edge right assignment $0,1$, Turn into $0-1$ Shortest path problem , And then run straight $dijkstra$ that will do .

Code

#include <bits/stdc++.h>
#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<int, int>
#define mkp make_pair
#define fir first
#define sec second

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

struct node{
    
    int fa, to, res, id;
    const bool operator< (const node &x) const {
     return res > x.res; }
};

priority_queue<node> pq;

void dijkstra(){
    
    for(int i = 0; i < 4; i++){
    
        auto &[v, k] = g[s1][i];
        if(v == s2) pq.emplace(node{
    s1, s2, 0, k});
    }
    while(pq.size()){
    
        auto now = pq.top(); pq.pop();
        if(now.to == 0 || dis[now.id] != -1) continue;
        dis[now.id] = now.res;
        for(int i = 0; i < 4; i++){
    
            auto &[to, k] = g[now.to][i];
            if(to == now.fa) pq.emplace(node{
    now.to, g[now.to][(i + 1) % 4].fir, now.res, g[now.to][(i + 1) % 4].sec});
            else pq.emplace(node{
    now.to, g[now.to][(i + 1) % 4].fir, now.res + 1, g[now.to][(i + 1) % 4].sec});
        }
    }
}

void solve(){
    
    cin >> n;
    memset(dis, -1, sizeof(dis));
    for(int i = 1; i <= n; i++){
    
        for(int j = 0; j < 4; j++){
    
            int v; cin >> v;
            g[i].emplace_back(mkp(v, ++cnt));
        }
    }
    cin >> s1 >> s2 >> t1 >> t2;
    dijkstra();
    for(int i = 0; i < 4; i++){
    
        auto &[to, k] = g[t1][i];
        if(to == t2) cout << dis[k] << endl;
    }
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}