题目

题目背景
多年以后，我在搬砖的工地上，远远望见了一个身影：仍然是如同漆黑的杆子一般，手丝毫不摆动，而脚一步一印往前挪动，像吸盘，像祂正试图学会在地上平移，用自己的脚。

我几乎要失声叫出祂的名字；这个名字我花了十年去恐惧，花了十年去遗忘，但我看到祂的一瞬间，所有努力都是徒劳，所有意义都被抹杀。

任何事物都逃不过祂的眼睛。当我从惊慌中挣脱出来，抬头便遇上祂的审视。祂胸前的金牌扰乱着我的神志。我只能勉强从牙缝中挤出来几个字：

“普……普林斯普！”

祂的嘴唇没有动，我的脑海中却响起一句话。这真的是我刚刚所顿悟的么？

“校长笑话，烟雾弹也；水群摆烂，麻痹对手尔。”

回忆如波涛翻滚。仿佛有无数个祂同时在我耳边低语：

“你看，你又被骗了吧。”

题目描述
给出一个无向连通图 $G=(V,E)$，定义新图 $G^{\prime }=(V,E^{\prime })$ 满足 E ′ = { ⟨ a , b , c a ⟩ ∣ dis ( a , b ) ⩽ d a } E'=\{\langle a,b,c_a\rangle\mid\text{dis}(a,b)\leqslant d_a\} E′={⟨a,b,ca​⟩∣dis(a,b)⩽da​}，其中 $⟨a,b,c⟩$ 表示边权为 $c$ 的 $a\to b$ 有向边，而 $\text{dis}(a,b)$ 为 $G$ 上 $a,b$ 最短路的边数。

求新图 $G^{\prime }$ 上 $1$ 号点到每个点的最短路。

数据范围与约定
$n⩽2\times 10^5\wedge d_i\in [1,n]\wedge c_i\in [1,10^9]\wedge |E|⩽|V|+50$ 。时限 $4\mathrm{s}$ 。

思路

注意到 $|E|⩽|V|+50$，考虑建一棵生成树，然后讨论非树边的影响。必要条件是搞懂树边的影响。即，先考虑原图是一棵树的情况。

树上路径问题？类似此题，可以直接点分治优化建图。不需要边分治，因为 $\text{dis}(y,z)⩽d_x-\text{dis}(x,z)$ 是 $x\to y$ 有边的充分条件，即 $\text{dis}(x,y)$ 可以实际上不经过 $z$，不需要边分治来保障 “必须经过” 的要求。

当然，现在想想，优化建图跑最短路，不如 $\mathsf{O}\mathsf{U}\mathsf{Y}\mathsf{E}$ 所说 数据结构优化转移。建出显式图，只会增加不必要的时空复杂度。非最短路问题，倒是有可能让代码实现更简单（比如 $\text{2-sat}$ 问题）。

非树边呢？相当于转移过程中，需要走过某条非树边。点分治的本质是，考虑 $\text{dis}$ 必须经过某个点；将每条非树边的任一端点设为 “特殊点”，对经过特殊点的 $\text{dis}$ 进行转移即可。

显式建图，似乎有 $\mathcal{O}(n\log n+nk)$ 条边，其中 $k=|E|-|V|+1$ 。跑 $\mathtt{d}\mathtt{i}\mathtt{j}\mathtt{k}\mathtt{s}\mathtt{t}\mathtt{r}\mathtt{a}$ 岂不是 $\mathcal{O}[n\log n\log (n\log n)]$ 了吗？可以类比此题，将 $(v_i+c_i)$ 放入 $\mathtt{h}\mathtt{e}\mathtt{a}\mathtt{p}$ 中；显式建图，则其等价于将边权为 $0$ 的连通块进行 $\mathrm{b}\mathrm{f}\mathrm{s}$ 更新。这样可以保证每个点直接得到答案，复杂度 $\mathcal{O}(n\log n+nk)$ 。

代码

#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // (the STRONG LONG for loneliness)
#include <cctype> // DDG yydDOG & ZXY yydBUS !!!
#include <queue>
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){int a = 0, c = getchar(), f = 1;for(; !isdigit(c); c=getchar())if(c == '-') f = -f;for(; isdigit(c); c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}const int MAXN = 200005, MAXM = 200055;
# define _go(i,x) for(int i=head[x]; ~i; i=e[i].nxt)
struct Edge{ int to, nxt; };
Edge e[MAXN<<1]; int head[MAXN], cntEdge;
void addEdge(int a, int b){e[cntEdge].to = b, e[cntEdge].nxt = head[a];head[a] = cntEdge ++;
}
const int LOGN = 18;
int siz[MAXN], dep[LOGN][MAXN], fa[MAXN][LOGN];
bool vis[MAXN]; int whole, core;
void findRoot(int x, int pre){siz[x] = 1; int mx = 0;_go(i,x) if((i^1) != pre && !vis[e[i].to]){findRoot(e[i].to,i), siz[x] += siz[e[i].to];mx = std::max(mx,siz[e[i].to]);}if((mx<<1) <= whole && whole <= (siz[x]<<1)) core = x;
}
int *group[MAXN];
int* collect(const int &level, int x, int pre, int* ptr){fa[x][level] = core, *(ptr ++) = x;_go(i,x) if((i^1) != pre && !vis[e[i].to]){dep[level][e[i].to] = dep[level][x]+1;ptr = collect(level,e[i].to,i,ptr);}return ptr;
}
void solve(int x, int level){static int buc[MAXN], tmp[MAXN]; ///< bucket sortfindRoot(x,-1), memset(buc,0,whole<<2);dep[level][core] = 0, collect(level,core,-1,tmp);rep0(i,0,whole) ++ buc[dep[level][tmp[i]]];rep0(i,1,whole) buc[i] += buc[i-1];group[core] = new int[whole+1];*group[core] = core, group[core][whole] = -1;for(int *i=tmp+1; i!=tmp+whole; ++i){int &rnk = buc[dep[level][*i]-1];group[core][rnk ++] = *i;}vis[core] = true;const int _core = core;_go(i,core) if(!vis[e[i].to]){if(siz[e[i].to] > siz[_core])whole = siz[x]-siz[_core];else whole = siz[e[i].to];solve(e[i].to,level+1);}
}void bfs(int *que, int *dis, int x, const int &n){memset(dis+1,-1,n<<2), dis[x] = 0;int *bac = que; *bac = x;for(; que!=bac+1; ++que) // keep releasing_go(i,x=*que) if(!(~dis[e[i].to])){dis[e[i].to] = dis[x]+1;++ bac, *bac = e[i].to;}
}namespace UFS{int fa[MAXN];int find(int a);bool merge(int a, int b);
}
bool bad[MAXN]; int tot;
const int MAXK = 102;
int dis[MAXK][MAXN], que[MAXK][MAXN];
int *que_ptr[MAXK];typedef std::pair<llong,int> PII;
llong ans[MAXN]; extern bool vis[MAXN];
std::priority_queue<PII> pq;
int radius[MAXN], cost[MAXN];
int main(){int n = readint(), m = readint();rep(i,1,n) UFS::fa[i] = i;memset(head+1,-1,n<<2);std::queue< std::pair<int,int> > bad_edge;for(int i=1,a,b; i<=m; ++i){a = readint(), b = readint();if(UFS::merge(a,b))addEdge(a,b), addEdge(b,a);else{bad[a] = bad[b] = true;bad_edge.push(std::make_pair(a,b));}}whole = n, solve(1,0); memset(vis+1,false,n);for(; !bad_edge.empty(); bad_edge.pop()){const std::pair<int,int> &p = bad_edge.front();addEdge(p.first,p.second), addEdge(p.second,p.first);}rep(i,1,n) if(bad[i]) bfs(que[tot],dis[tot],i,n), ++ tot;rep0(i,0,tot) que_ptr[i] = que[i];rep(i,1,n){radius[i] = readint();cost[i] = -readint(); // negated}ans[1] = 0, vis[1] = true;pq.push(PII{cost[1],1});while(!pq.empty()){int x = pq.top().second; pq.pop();rep0(j,0,LOGN) if(fa[x][j]) // existfor(int* &i=group[fa[x][j]]; ~(*i); ++i){if(dep[j][*i]+dep[j][x] > radius[x]) break;if(vis[*i]) continue; // updatedans[*i] = ans[x]+cost[x], vis[*i] = true;pq.push(PII{ans[*i]+cost[*i],*i});}rep0(j,0,tot) for(int* &i=que_ptr[j]; i!=que[j]+n; ++i){if(dis[j][*i]+dis[j][x] > radius[x]) break;if(vis[*i]) continue; // updatedans[*i] = ans[x]+cost[x], vis[*i] = true;pq.push(PII{ans[*i]+cost[*i],*i});}}rep(i,2,n) printf("%lld\n",-ans[i]);return 0;
}int UFS::find(int a){if(a == fa[a]) return a;return fa[a] = find(fa[a]);
}
bool UFS::merge(int a, int b){if(find(a) == find(b)) return false;fa[fa[a]] = fa[b]; return true;
}