sol
先预处理每个状态是否合法。记(dis[i][j])表示从任意一个绝招点到达左手在(i)右手在(j)这个状态的最小步数，以及(vis[i][j])表示是从哪一个绝招点转移过来的。这一步可以(bfs)实现，复杂度(O((n+m)^2))。
然后再枚举两个相邻状态，如果两个状态的(vis)不同，那么就可以更新这两个绝招点的答案。
可以理解为从每个绝招点开始扩张，当遇到“接壤”时即意味着两个绝招点在最短路上相遇。
code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
#define cmin(a,b) (a>b?a=b:a)
const int N = 1005;
struct Graph{
int to[N*10],nxt[N*10],head[N],cnt;
void link(int u,int v){
to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt;
}
}G1,G2;
int n,m,k,mn,mx,x[N],y[N],ok[N][N],q[2][N*N],hd,tl,vis[N][N],dis[N][N],ans[N*100];
int main(){
n=gi();m=gi();mn=gi();mx=gi();
for (int i=1;i<=n;++i) x[i]=gi(),y[i]=gi();
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j){
int len=abs(x[i]-x[j])+abs(y[i]-y[j]);
if (len>=mn&&len<=mx) ok[i][j]=1;
}
k=gi();
for (int i=1;i<=k;++i){
q[0][i]=gi();q[1][i]=gi();
vis[q[0][i]][q[1][i]]=i;
}
for (int i=1;i<=m;++i){
int u=gi(),v=gi(),t=gi();
if (!t) G1.link(u,v),G1.link(v,u);
else G2.link(u,v),G2.link(v,u);
}
for (int i=1;i<=n;++i) G1.link(i,i),G2.link(i,i);
hd=1,tl=k;
while (hd<=tl){
int u=q[0][hd],v=q[1][hd++];
for (int i=G1.head[u];i;i=G1.nxt[i])
for (int j=G2.head[v];j;j=G2.nxt[j]){
int uu=G1.to[i],vv=G2.to[j];
if (!ok[uu][vv]||vis[uu][vv]) continue;
vis[uu][vv]=vis[u][v];dis[uu][vv]=dis[u][v]+1;
q[0][++tl]=uu;q[1][tl]=vv;
}
}
memset(ans,63,sizeof(ans));
for (int u=1;u<=n;++u)
for (int v=1;v<=n;++v)
for (int i=G1.head[u];i;i=G1.nxt[i])
for (int j=G2.head[v];j;j=G2.nxt[j]){
int uu=G1.to[i],vv=G2.to[j];
if (!vis[u][v]||!vis[uu][vv]) continue;
if (vis[u][v]!=vis[uu][vv]){
int len=dis[u][v]+dis[uu][vv]+1;
cmin(ans[vis[u][v]],len);
cmin(ans[vis[uu][vv]],len);
}
}
for (int i=1;i<=k;++i) printf("%d
",ans[i]==ans[0]?-1:ans[i]);
return 0;
}