https://www.luogu.org/problemnew/show/P4473
仙人题啊仙人题
正解是什么并查集优化？？看不懂也不会写
读题发现，这题的问题在于暴力建边会GG,需要解决的就是一个点向一个连通块连边的问题
想到可以把连通块拆成一行一行，在一行内，要解决一个点向一个区间连边的问题
线段树优化连边，我们只建维护入边的线段树，对于一个区间找到对应线段树内节点连边，树内从父亲向儿子连边（边权当然是0）
nm个点，e=n^2mlogm = 16875000个边，这样跑一边最短路是O(eloge)，似乎能过？？？
然后就是我的zz时间：这个图不是无向的，因此x->y和y->x显然不同，得挨个点跑一边最短路才行...
我好菜qaq
2.0h
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #include<iostream> using namespace std; #define O(x) cout << #x << " " << x << endl; #define O_(x) cout << #x << " " << x << " "; #define B cout << "breakpoint" << endl; typedef long long ll; typedef pair<ll,int> pii; const ll inf = 1e14; #define mp make_pair inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } const int maxn = 303; const int N = 1e6 + 5; int n,m; int id[maxn][maxn];//id[i][j] : i行j列对应线段树中哪个节点 int ls[N],rs[N],root[maxn],tot; struct egde { int to,next; ll cost; }e[N * 20]; int fir[N],alloc; void adde(int u,int v,int w) { e[++alloc].next = fir[u]; fir[u] = alloc; e[alloc].to = v; e[alloc].cost = w; } int build(int line,int i,int l,int r) { if(l == r) { id[line][l] = i; return i; } int mid = l + r >> 1; ls[i] = build(line,++tot,l,mid); rs[i] = build(line,++tot,mid + 1,r); adde(i,ls[i],0); adde(i,rs[i],0); return i; } void add(int i,int l,int r,int u,int ql,int qr,ll w)//u->[ql,qr] { if(l == ql && r == qr) { adde(u,i,w); return; } int mid = l + r >> 1; if(qr <= mid) add(ls[i],l,mid,u,ql,qr,w); else if(ql > mid) add(rs[i],mid + 1,r,u,ql,qr,w); else add(ls[i],l,mid,u,ql,mid,w),add(rs[i],mid + 1,r,u,mid + 1,qr,w); } bool vis[N]; ll dis[N]; void dij(int s) { for(int i = 1;i <= tot;i++) dis[i] = inf; memset(vis,0,sizeof(vis)); dis[s] = 0; priority_queue<pii,vector<pii>,greater<pii> > p; p.push(mp(dis[s],s)); while(p.size()) { pii t = p.top(); p.pop(); int u = t.second; if(vis[u]) continue; vis[u] = 1; for(int i = fir[u];i;i = e[i].next) { int v = e[i].to; ll w = e[i].cost; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if(!vis[v]) p.push(mp(dis[v],v)); } } } } int b[maxn][maxn]; ll a[maxn][maxn]; int main() { n = read(),m = read(); for(int i = 1;i <= n;i++) root[i] = build(i,++tot,1,m); for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) b[i][j] = read();//距离 for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) scanf("%lld",&a[i][j]);//费用 for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) { for(int k = max(1,i - b[i][j]);k <= min(n,i + b[i][j]);k++) { int res = b[i][j] - abs(k - i); add(root[k],1,m,id[i][j],max(1,j - res),min(m,j + res),a[i][j]); } } int x1 = read(),y1 = read(),x2 = read(),y2 = read(),x3 = read(),y3 = read(); int x = id[x1][y1],y = id[x2][y2],z = id[x3][y3]; dij(x); ll xy = dis[y],xz = dis[z]; dij(y); ll yz = dis[z],yx = dis[x]; dij(z); ll zx = dis[x],zy = dis[y]; ll ansx = yx + zx,ansy = xy + zy,ansz = xz + yz; if(ansx >= inf && ansy >= inf && ansz >= inf) { printf("NO "); return 0; } if(ansx <= ansy && ansx <= ansz) printf("X %lld",ansx); else if(ansy <= ansx && ansy <= ansz) printf("Y %lld",ansy); else printf("Z %lld",ansz); }