又见神题= = 这其实是最短路的变形，我们用bfs来跑最短路，然后用map存一下状态，判断有没有重复走。然后最短路的话稍微有一点不一样，从当前点到下一个点有两种路径，如果倒着走就要用现有路径减去，正着走就直接加。 每一次将新的点加入队列答案都加一（显然），当下一个点为1时而且路径不为0（防止你一开始走出去就折返回来），就输出答案。
#include<cstdio> #include<algorithm> #include<cstring> #include<map> #include<queue> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; typedef pair<int,int> P; const int N=5e3+5; const int M=1e5+5; int go[M],next[M],head[M],n,m; int a[M]; map<P,int>t; queue<P> q; int tot; inline void add(int x,int y) { go[++tot]=y; next[tot]=head[x]; head[x]=tot; } int main() { scanf("%d%d",&n,&m); fo(i,1,n)scanf("%d",&a[i]); fo(i,1,m) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } q.push(P(1,0)); t[P(1,0)]=1; while (!q.empty()) { P x=q.front(); int y=t[x]; q.pop(); for(int i=head[x.first];i;i=next[i]) { int j=(a[x.first]-a[go[i]]+360)%360; int k=(a[go[i]]-a[x.first]+360)%360; P z(go[i],j<k?x.second+j:x.second-k); if (t[z])continue; if (go[i]==1&&z.second) { printf("%d\n",y); return 0; } q.push(z),t[z]=y+1; } } printf("-1\n"); return 0; }