首页分享每日一题之 hiho199 积水的城市2

每日一题之 hiho199 积水的城市2

来源：花匠小妙招时间：2025-02-17 18:10

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

描述

提示：本题与“积水的城市”相比，数据范围扩大了。

如下图所示，某市市区由M条南北向的大街和N条东西向的道路组成。其中由北向南第i条路和第i+1条路之间的距离是Bi (1 <= i < N)，由西向东第i条街和第i+1条街之间的距离是Ai (1 <= i < M)。

小Ho现在位于第x条路和第y条街的交叉口，他的目的地是第p条路和第q条街的交叉口。由于连日降雨，城市中有K个交叉口积水太深不能通行。小Ho想知道到达目的地的最短路径的长度是多少。

输入

第一行包含两个整数N和M。(1 <= N, M <= 1000)

第二行包含N-1个整数, B1, B2, B3, … BN-1。(1 <= Bi <= 100000)

第三行包含M-1个整数, A1, A2, A3, … AM-1。(1 <= Ai <= 100000)

第四行包含一个整数K，表示积水的交叉口的数目。 (1 <= K <= 30)

以下K行每行包含2个整数，X和Y，表示第X条街和第Y条路的交叉口积水。(1 <= X <= N, 1 <= Y <= M)

第K+5行包含一个整数Q，表示询问的数目。 (1 <= Q <= 1000)

以下Q行每行包含4个整数x, y, p, q，表示小Ho的起止点。起止点保证不在积水的交叉口处。 (1 <= x, p <= N, 1 <= y, q <= M)

输出

对于每组询问，输出最短路的长度。如果小Ho不能到达目的地，输出-1。

样例输入

4 5 2 4 1 3 3 3 2 3 1 3 2 3 3 2 1 1 2 2 4 样例输出

24 思路：

这道题的数据范围很大，所以不能用《积水的城市》里直接建图SPFA的解法。

突破口在于积水的交叉口数目K很小，只有30。所以直观上看整个城市中是有大片区域没有障碍的。对于两个交叉路口A和B，如果它们之间一处积水都没有，那么它们之间的最短路就是哈密顿距离（横纵坐标差的和）。

具体的解法 hdu_toraoh 有一篇很好的题解，分享给大家：在线笔试题解题报告系列hihocoder #1368 积水的城市2
上述题解有一处错误。只对最左的关键点(起点、终点、积水点)，把x-1加入到x关键值中是不够的。我们需要对所有关键点(x, y)，将x,x-1,x+1都加入到x关键值中。(对y坐标也做相同处理)

#include <iostream> #include <queue> #include <cstring> #include <algorithm> #include <map> #include <queue> using namespace std; const int M = 1e3+5; const int INF = 1e9+5; int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; struct Point { int x,y; Point () {} Point (int a,int b):x(a),y(b){} Point go(int i) { return Point(x+dir[i][0],y+dir[i][1]); } bool is_ok(int n,int m) { return x >= 1 && x <= n && y >= 1 && y <= m; } }; int Alength[M],Blength[M]; int K; int cross[35][2]; map<int,int>xaxis,yaxis; long long dist[105][105]; bool walk[105][105]; int colLength[105]; int rowLength[105]; long long solve(int xa,int ya,int xb,int yb) { int n = xaxis.size(),m = yaxis.size(); dist[xa][ya] = 0; queue<Point> q; q.push(Point(xa,ya)); while(!q.empty()) { Point x = q.front(); q.pop(); long long disy, disx = dist[x.x][x.y]; for (int i = 0; i < 4; ++i) { Point y = x.go(i); if (y.is_ok(n,m) && walk[y.x][y.y]) { if (i == 0) { disy = disx + colLength[y.x+1]; } else if (i == 1) { disy = disx + colLength[y.x]; } else if (i == 2) { disy = disx + rowLength[y.y]; } else disy = disx + rowLength[y.y+1]; if (disy < dist[y.x][y.y]) { dist[y.x][y.y] = disy; q.push(y); } } } } if (dist[xb][yb] == (long long)INF*1000) return -1; else return dist[xb][yb]; } void addnode(int v, map<int,int> &axis) { axis[v-1] = 1; axis[v] = 1; axis[v+1] = 1; } void fix(map<int,int> &axis,int n, int *oriLength,int *Length) { int cnt = 0; map<int,int>::iterator it = axis.begin(); for(;it=axis.begin(),it->first<1;axis.erase(it)); it=axis.begin(); if(it->first>1) axis[(it->first)-1]=1; for (;it = axis.end(),--it,it->first > n;axis.erase(it)); it=axis.end();--it; if(it->first<n) axis[(it->first)+1]=1; fill(Length,Length+105,0); for (it = axis.begin(); it != axis.end(); ++it) { it->second = ++cnt; if (cnt != 1) { map<int,int>::iterator pit = it; --pit; Length[cnt] = oriLength[it->first] - oriLength[pit->first]; } } } int main() { int n,m,x,y; cin >> n >>m; for (int i = 2; i <= n; ++i) { cin >> Alength[i]; Alength[i] += Alength[i-1]; } for (int i = 2; i <= m; ++i) { cin >> Blength[i]; Blength[i] += Blength[i-1]; } cin >> K; for (int i = 0; i < K; ++i) cin >> cross[i][0] >> cross[i][1]; int Q,xa,ya,xb,yb; cin >> Q; while(Q--) { cin >> xa >> ya >> xb >> yb; xaxis.clear(); yaxis.clear(); addnode(xa,xaxis); addnode(xb,xaxis); addnode(ya,yaxis); addnode(yb,yaxis); for(int i=0;i<K;++i){ addnode(cross[i][0],xaxis); addnode(cross[i][1],yaxis); } fix(xaxis,n,Alength,colLength); fix(yaxis,m,Blength,rowLength); fill(dist[0],dist[100]+101,(long long)INF*1000); memset(walk,1,sizeof(walk)); for(int i=0;i<K;++i){ walk[xaxis[cross[i][0]]][yaxis[cross[i][1]]]=0; } cout << solve(xaxis[xa],yaxis[ya],xaxis[xb],yaxis[yb]) << endl; } return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189