J - Journey
给定一个城市有若干十字路口,右转不需要等红灯,直行、左转和掉头都需要,求起点到终点最少等几次红灯。
把每条路看做点,十字路口处连边,向右边权为 $0$,其他为 $1$,跑最短路。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> mp;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<array<int, 2>>> g;
int m = 0;
auto Get = [&](int x, int y) {
if (!mp.count({x, y})) {
mp[{x, y}] = m++;
g.emplace_back();
}
return mp[{x, y}];
};
for (int i = 0; i < n; i++) {
vector<int> c(4);
vector<int> u(4), v(4);
for (int j = 0; j < 4; j++) {
cin >> c[j];
c[j]--;
u[j] = Get(c[j], i);
v[j] = Get(i, c[j]);
}
for (int j = 0; j < 4; j++) {
g[u[j]].push_back({v[(j + 1) % 4], 0});
for (int k = 0; k < 4; k++) {
if ((j + 1) % 4 != k) {
g[u[j]].push_back({v[k], 1});
}
}
}
}
int s1, s2, t1, t2;
cin >> s1 >> s2 >> t1 >> t2;
s1--, s2--, t1--, t2--;
const int inf = numeric_limits<int>::max();
deque<int> que;
vector<int> dist(m, inf);
vector<int> vis(m);
que.push_back(Get(s1, s2));
dist[Get(s1, s2)] = 0;
while (!que.empty()) {
auto u = que.front();
que.pop_front();
if (vis[u]) {
continue;
}
vis[u] = 1;
for (auto [v, w] : g[u]) {
if (w == 1) {
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
que.push_back(v);
}
} else {
if (dist[v] > dist[u]) {
dist[v] = dist[u];
que.push_front(v);
}
}
}
}
int ans = dist[Get(t1, t2)];
if (ans == inf) {
ans = -1;
}
cout << ans << '\n';
return 0;
}