(2022 Niuke multi school III) j-journey (Dijkstra)

subject ：

  The sample input ：

4
3 4 0 0
0 0 4 3
2 1 0 0
2 0 0 1
4 2 4 1

Sample output ：

1

The question ： There are several intersections in a given city , Do you need to wait for the red light to turn right , Go straight 、 Both left turns and U-turns require activities , How many red lights are required to wait at least from the start to the end .

analysis ： We can Regard each edge with direction as a point , Be careful The two directions of an edge are regarded as two different points , After dealing with these things, we can use dijkstra Just run the shortest way

The important thing is how to build a map , For an edge, if it has not been recorded before, we can directly regard it as a point , But how do we know that the weight of the edge between the current point and other points is 1 Still for 0, This requires drawing and thinking , For example, we are now with t The intersection adjacent to the point is 1 Intersection No , So if (t,1) yes t The first side of the intersection , Then we can find out (1,t) yes 1 Which side of intersection No , Then the next side of the current side is (t,1) Right turn side , Then build one of these two edges with a weight of 0 Just the side of , Notice that we are abstracting edges into points , And The established edge is a unidirectional edge , as for 1 We will (t,1) Establish a line with the other three sides with a length of 1 Just the side of , That's it. We'll finish the drawing , Then you can find the answer by running the shortest path from the starting point .

See code for details ：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<unordered_map>
using namespace std;
typedef pair<int,int> PII;
#define int long long
unordered_map<long long,int>mp;
const int N=5e6+10,M=5e7+10;
int p[N][4];
int h[N],ne[M],e[M],w[M],idx;
int be,en,d[N];
bool vis[N];
void add(int x,int y,int z)
{
	e[idx]=y;
	w[idx]=z;
	ne[idx]=h[x];
	h[x]=idx++;
}
int dijkstra(int x)
{
    memset(d,0x3f,sizeof(d)); 
    d[x]=0;
    priority_queue<PII,vector<PII>,greater<PII> >q; 
    q.push({0,x});
    while(!q.empty())
    {
        int begin=q.top().second;
        q.pop();
        if(vis[begin]) continue;
        vis[begin]=true;
        for(int i=h[begin];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]>d[begin]+w[i])
                {
                    d[j]=d[begin]+w[i];
                    q.push({d[j],j});
                }
        }
    }
    if(d[en]==0x3f3f3f3f3f3f3f3f) return -1;
    return d[en];
}
signed main()
{
	int n;
	cin>>n;
	int tt=0;
	for(int i=1;i<=n;i++)
		scanf("%lld%lld%lld%lld",&p[i][0],&p[i][1],&p[i][2],&p[i][3]);
	for(int i=1;i<=4*n;i++) h[i]=-1;// Note that the number of points here is not n, We abstract each edge into a point 
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<4;j++)
		{
			int t=p[i][j];
			if(t)
			{
				if(!mp[1ll*i*1e9+t]) mp[1ll*i*1e9+t]=++tt;
				int k=0;
				for(;k<4;k++)
					if(p[t][k]==i) break;
				k=(k+1)%4;
				if(!mp[t*1e9+p[t][k]]) mp[t*1e9+p[t][k]]=++tt;
				add(mp[i*1e9+t],mp[t*1e9+p[t][k]],0);
				for(int l=1;l<4;l++)
				{
					k=(k+1)%4;
					if(!mp[t*1e9+p[t][k]]) mp[t*1e9+p[t][k]]=++tt;
					add(mp[i*1e9+t],mp[t*1e9+p[t][k]],1);
				}
			}
		}
	}
	int a,b,c,d;
	scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
	be=mp[a*1e9+b];
	en=mp[c*1e9+d];
	cout<<dijkstra(be);
	return 0;
}