Niuke multi school -journey- (map building distra+ card often optimization)

J

The question ：
It's for you. n A crossroads , There are four directions at each intersection , Mark your intersection counterclockwise , If it is 0 The sign means there is no intersection . Then every time you turn right at the intersection, it doesn't cost , And move on , Turn left , Overturn , It's all cost 1. First, you are A The intersection faces B On the road at the intersection , Let you walk to C The intersection faces D On the road at the intersection . Ask you the least cost . The direction you face is unnecessary ,A Yes B and B Yes A It's different .

reflection ：
In fact, this question , Give you the intersection , I didn't give you a designated direction , Just in reverse order . If you run the shortest way at the intersection, you will find this diagram difficult to get . So run by the side , That is, regard the edge as a point , Look at these edges as different points , Conduct hash. How did you think of it , Because it's about the cost of walking from one road to another , So it's easier to take the road as a point . When building a map, it is to enumerate four intersections of an intersection , Then find two intersections , Build a map for them , If it's a right turn, it doesn't cost .
Then it is worth noting that , use map<PII,int> Hash will timeout , Then change to unordered_map<PII,int,cmp>. This cmp Overload usage is different, there will be timeout and no timeout . Of course, the safest thing is not to build a map , Run straight , Just enumerate where you go when you run . When hashing, hash the edge into a particularly large value and put it in unordered_map<int,int> That's all right. .

Code ：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 5e6+10,M = 2010;

int T,n,m,k;
int va[N][4];
int dist[N],vis[N];

struct cmp{
    
	int operator()(PII A)const{
    
		return A.fi*521417+A.se;
	}
};

int cnt;
unordered_map<PII,int,cmp> mp;

vector<PII > e[N];

void distra(int A)
{
    
	for(int i=1;i<=cnt;i++) dist[i] = inf;
	priority_queue<PII,vector<PII>,greater<PII> > q;
	q.push({
    0,A});
	dist[A] = 0;
	while(q.size())
	{
    
		auto t = q.top();q.pop();
		int now = t.se,dis = t.fi;
		if(vis[now]) continue;
		for(auto tt:e[now])
		{
    
			int spot = tt.fi,w = tt.se;
			if(dist[spot]>dist[now]+w)
			{
    
				dist[spot] = dist[now]+w;
				q.push({
    dist[spot],spot});
			}
		}
	}
}

signed main()
{
    
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
    
		for(int j=0;j<4;j++)
		{
    
			cin>>va[i][j];
			if(!va[i][j]) continue;
			int a = i,b = va[i][j];
			if(!mp[{
    a,b}]) mp[{
    a,b}] = ++cnt;
			if(!mp[{
    b,a}]) mp[{
    b,a}] = ++cnt;
		}
		for(int j=0;j<4;j++)
		{
    
			if(!va[i][j]) continue;
			for(int k=0;k<4;k++)
			{
    
				if(!va[i][k]) continue;
				int a = va[i][j],b = i,c = va[i][k],w = 1;
				if((j+1)%4==k) w = 0;
				int x = mp[{
    a,b}],y = mp[{
    b,c}];
				e[x].pb({
    y,w});
			}
		}
	}
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	distra(mp[{
    A,B}]);
	if(dist[mp[{
    C,D}]]==inf) cout<<-1;
	else cout<<dist[mp[{
    C,D}]];
	return 0;
}

summary ：
Try more , I feel map When it doesn't work ,unordered Not good either. , I don't want to write . Little by little optimization , Maybe it's over in the end .