1 条题解
-
0
#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
- 上传者