💡题解与思路（含公式）

📌转化思路：

将每个航线视为一条有向边，方向由顺时针判断，并附带方向上的角度增量值。

构建有向图时，每条边保存以下信息：

节点 $u \rightarrow v$

是否顺时针：根据经度计算

顺时针角度差：例如从 $350 \rightarrow 10$ 是 $20^\circ$ 顺时针

🔍核心思路：

构建图后，需要找出一条回到起点的路径，满足：

路径上的航班数最少；

顺时针总角度 $\ne$ 逆时针总角度，即不能走完 $0^\circ$ 或者走一条不绕圈的路径。

🧠算法设计（双权值最短环）：

图构建：

每条边加入两个方向（双向）；

计算每条边的顺时针角度增量 $d$；

图遍历（例如 BFS + 状态记录）：

每个状态记录当前所在节点、已走的顺时针角度总和 mod 360、步数；

BFS 搜索回到起点（节点 1）且顺逆角度不等的路径；

输出所需最少步数。

📐判断顺时针角度的方法：

设两个经度为 $a$ 和 $b$：

cpp int clockwise_angle(int a, int b) { return (b - a + 360) % 360; } 如果顺时针角度 $< 180$，则方向为顺时针；否则为逆时针。

✅总结

模拟地球上的点→图中节点；

航线→带方向的边；

判断是否形成一圈→累计顺时针角度是否 $\ne 0$；

使用 BFS 或 DFS 寻找最短的满足条件的回路。

代码实现

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
#define N 5001
int a[N];
vector<int> adj[N];
set<int> se[N];//判重 se[i] 标记航班到达i点所旋转的角度有哪些
struct Node
{
	int pos,x,cnt;
}que[500000];
int Bfs()              //BFS 搜索 关键在于判重
{ 
	Node now,next;
	now.pos=1;
	now.x=0;
	now.cnt=0;
	se[1].insert(0);
	int front=0,rear=0;
	int u,v,tx;
	que[rear++]=now;
	while(front<rear)
	{
		now=que[front++];
		u=now.pos;
		for(int i=0;i<adj[u].size();i++)
		{
			v=adj[u][i];
			tx=a[u]-a[v];
			if(tx>180) tx-=360;
			if(tx<-180) tx+=360;
			tx+=now.x;
			if(se[v].find(tx)==se[v].end())   //判重条件
			{
				if(v==1) return now.cnt+1;
				se[v].insert(tx);
				next.pos=v;
				next.x=tx;
				next.cnt=now.cnt+1;
				que[rear++]=next;
			}
		}
	}
	return -1;
}
int main()
{
	int n,m;   //n个城市，m条边，给定每个城市的经度，遵循最短原则，然后遍历一周回来，求最少要做多少次航班 
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++)            //横向判重
		{
			adj[i].clear();
			se[i].clear();
			scanf("%d",&a[i]);
		}
		
		int u,v;
		for(int i=0;i<m;i++)              //纵向判重
		{
			scanf("%d%d",&u,&v);
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		printf("%d\n",Bfs());
	}
	return 0;
}