上传网站内容,网站开发与推广计划书,汽车网站制作,网络运营商哪家好I - Robots
显然可以两点之间能连边就连边#xff0c;但是边数会很多#xff0c;考虑优化 对于三个点(x0,y0)(x_0,y_0)(x0,y0)#xff0c;(x0,y1)(x_0,y_1)(x0,y1)#xff0c;(x0,y2)(x_0,y_2)(x0,y2)
如果三个点的方向都是UUU 那么没有必要1→31\to 31→3连…I - Robots
显然可以两点之间能连边就连边但是边数会很多考虑优化 对于三个点(x0,y0)(x_0,y_0)(x0,y0)(x0,y1)(x_0,y_1)(x0,y1)(x0,y2)(x_0,y_2)(x0,y2)
如果三个点的方向都是UUU 那么没有必要1→31\to 31→3连边只需要让222作为中转站连边即1→2→31\to 2\to 31→2→3连边即可。
这样边数就是线性的。
upd向上面建图不难发现每个点只会和启动它的点连一条边因此边数是O(n)O(n)O(n)量级的
#includebits/stdc.h
using namespace std;
constexpr int N100010;
struct node
{int x,y;char d;
}a[N];
int b[2*N],n,m;
vectorpairint,int gx[2*N];
vectorpairint,int gy[2*N];
long long d[N];
long long T;
bool vis[N];
void dijkstra()
{priority_queuepairlong long,int,vectorpairlong long,int,greaterpairlong long,intq;memset(d,0x3f,sizeof d);q.push({0,1});d[1]0;while(q.size()){int uq.top().second; q.pop();if(vis[u]) continue;vis[u]1;if(a[u].dU){vectorpairint,int ::iterator itlower_bound(gx[a[u].x].begin(),gx[a[u].x].end(),(pairint,int){a[u].y,u});it;while(it!gx[a[u].x].end()){int vit-second;if(d[v]d[u]b[a[v].y]-b[a[u].y]){d[v]d[u]b[a[v].y]-b[a[u].y];q.push({d[v],v});}if(a[v].dU) break;it;}}if(a[u].dD){vectorpairint,int ::iterator itlower_bound(gx[a[u].x].begin(),gx[a[u].x].end(),(pairint,int){a[u].y,u});if(itgx[a[u].x].begin()) continue;--it;while(1){int vit-second;if(d[v]d[u]-b[a[v].y]b[a[u].y]){d[v]d[u]-b[a[v].y]b[a[u].y];q.push({d[v],v});}if(a[v].dD) break;if(itgx[a[u].x].begin()) break;it--;}}if(a[u].dR){vectorpairint,int ::iterator itlower_bound(gy[a[u].y].begin(),gy[a[u].y].end(),(pairint,int){a[u].x,u});it;while(it!gy[a[u].y].end()){int vit-second;if(d[v]d[u]b[a[v].x]-b[a[u].x]){d[v]d[u]b[a[v].x]-b[a[u].x];q.push({d[v],v});}if(a[v].dR) break;it;}}if(a[u].dL){vectorpairint,int ::iterator itlower_bound(gy[a[u].y].begin(),gy[a[u].y].end(),(pairint,int){a[u].x,u});if(itgy[a[u].y].begin()) continue;--it;while(1){int vit-second;if(d[v]d[u]-b[a[v].x]b[a[u].x]){d[v]d[u]-b[a[v].x]b[a[u].x];q.push({d[v],v});}if(a[v].dL) break;if(itgy[a[u].y].begin()) break;it--;}}}
}
int main()
{cinnT;for(int i1;in;i){int x,y;char d;cinxyd;a[i]{x,y,d};b[m]x;b[m]y;}sort(b1,b1m);munique(b1,b1m)-b-1;for(int i1;in;i){a[i].xlower_bound(b1,b1m,a[i].x)-b;a[i].ylower_bound(b1,b1m,a[i].y)-b;}for(int i1;in;i){gx[a[i].x].push_back({a[i].y,i});gy[a[i].y].push_back({a[i].x,i});}for(int i1;im;i) {sort(gx[i].begin(),gx[i].end());sort(gy[i].begin(),gy[i].end());}dijkstra();for(int i1;in;i){if(d[i]0x3f3f3f3f3f3f3f3f||Td[i])coutb[a[i].x] b[a[i].y]\n;else{long long xb[a[i].x],yb[a[i].y];if(a[i].dU) yT-d[i];if(a[i].dD) y-T-d[i];if(a[i].dR) xT-d[i];if(a[i].dL) x-T-d[i];coutx y\n;}}return 0;
}想到做法了但是以为可能还有数据能把边卡到2次方就帮队友调题去了~~非常可惜
