1 条题解

  • 0
    @ 2026-8-25 22:57:11
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=1e5+10,K=305;
    const int inf=0x3f3f3f3f3f3f3f3f;
    int f[K][K],h,w,n,x[K],h1[K],h2[K];
    struct node{int id,w;};
    signed main()
    {
    	scanf("%lld%lld%lld",&h,&w,&n);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%lld%lld%lld",&x[i],&h1[i],&h2[i]);
    	}
    	memset(f,0x3f,sizeof f); 
    	for(int i=1;i<=n;i++)
    	{
    		f[i][i]=0;
    		for(int j=1;j<=n;j++)
    		{
    			if(i==j) continue;
    			if(max(h1[i],h1[j])<=min(h2[i],h2[j]))
    				f[i][j]=f[j][i]=abs(x[i]-x[j]);
    		}
    	}
    	for(int k=1;k<=n;k++)
    		for(int i=1;i<=n;i++)
    			for(int j=1;j<=n;j++)
    				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    	int ques; scanf("%lld",&ques);
    	while(ques--)
    	{
    		int sh,sw,th,tw;
    		scanf("%lld%lld%lld%lld",&sw,&sh,&tw,&th);
            if(sh==th)// 记得特判
            {
                printf("%lld\n",abs(sw-tw));
                continue ;
            }
    		vector <node> sh_w,th_w;
    		for(int i=1;i<=n;i++)
    		{
    			if(h1[i]<=sh && sh<=h2[i])
    				sh_w.push_back({i,abs(x[i]-sw)});
    		}
    		for(int i=1;i<=n;i++)
    		{
    			if(h1[i]<=th && th<=h2[i])
    				th_w.push_back({i,abs(x[i]-tw)});
    		}
    		int res=inf;
    		for(node st:sh_w)
    		{
    			for(node ed:th_w)
    			{
    				int w=f[st.id][ed.id];
    				if(w==inf) continue;
    				w+=st.w+ed.w;
    				res=min(res,w);
    			}
    		}
    		int ans=(res==inf?-1:res+abs(sh-th));// 细节
    		printf("%lld\n",ans);
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    444
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    19
    已通过
    2
    上传者