题意：可以进行区间间互相连边与单点连边，求从某起点到所有点的最短距离。
先离线弄出树的形态，并保存可行的区间操作。
然后就是喜闻乐见的树剖+线段树优化了。
然而，毒瘤出题人把树剖卡成了不会tle便会mle。
我会说我考试时被卡成傻逼了么
于是预处理倍增进行连边即可，
#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<cmath> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N=5e4+10,M=13e5+10; struct node{ int u1,v1,u2,v2,w;node(){}; node(int _u1,int _v1,int _u2,int _v2,int _w){ u1=_u1,v1=_v1,u2=_u2;v2=_v2;w=_w; } }ql[M]; int n,m,s,t,tot,cnt,lg[N],f[N],dis[M<<1],d[N<<1],vis[M<<1],fa[N][16],in[N][16],out[N][16]; priority_queue<pair<int,int> >q;vector<int> g[N<<1];vector<pair<int,int> >edge[M<<1]; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } inline void add(int x,int y,int z){ edge[x].push_back(make_pair(y,z)); } inline void dijkstra(){ memset(dis,0x3f,sizeof(dis)); dis[s]=0;q.push(make_pair(0,s)); while(q.size()){ int x=q.top().second;q.pop(); if(vis[x]) continue;vis[x]=1; for(int i=0;i<edge[x].size();i++){ int y=edge[x][i].first,z=edge[x][i].second; if(dis[y]>dis[x]+z){ dis[y]=dis[x]+z;if(!vis[y]) q.push(make_pair(-dis[y],y)); } } } } inline int get(int x){ if(x==f[x]) return x;return f[x]=get(f[x]); } inline int lca(int x,int y){ if(d[x]>d[y]) swap(x,y); for(int i=15;~i;i--) if(d[fa[y][i]]>=d[x]) y=fa[y][i]; if(x==y) return x; for(int i=15;~i;i--) if(fa[y][i]!=fa[x][i]) y=fa[y][i],x=fa[x][i]; return fa[x][0]; } inline void dfs(int x,int fat){ fa[x][0]=fat;d[x]=d[fat]+1; in[x][0]=out[x][0]=x; for(int i=1;i<=15;i++){fa[x][i]=fa[fa[x][i-1]][i-1];} for(int i=1;(1<<i)<=d[x];i++){ in[x][i]=++cnt;out[x][i]=++cnt; add(in[x][i],in[x][i-1],0); add(out[x][i-1],out[x][i],0); add(in[x][i],in[fa[x][i-1]][i-1],0); add(out[fa[x][i-1]][i-1],out[x][i],0); } for(int i=0;i<g[x].size();i++){ int y=g[x][i];if(y==fat) continue; dfs(y,x); } } inline void build(int v1,int u1,int w,int k){ int j=0,u=u1,v; for(;(2<<(j))<=d[u1]-d[v1]+1;j++); int res=d[u1]-d[v1]+1-(1<<j); for(int i=20;~i;i--) if(res&(1<<i)) u=fa[u][i]; if(k) v=in[u][j];else v=out[u][j]; add(k?cnt:v,k?v:cnt,w); u=u1;if(k) v=in[u][j];else v=out[u][j]; add(k?cnt:v,k?v:cnt,w); } int main(){ n=read();m=read();s=read();cnt=n+1; for(int i=1;i<=n;i++) f[i]=i; for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for(int i=1;i<=m;i++){ int k=read(),u1=read(),v1=read(),u2,v2,w; if(k==1){ u2=read();v2=read();w=read(); if(get(u1)!=get(v1)||get(u2)!=get(v2)) continue; ql[++t]=node(u1,v1,u2,v2,w); } else if(k==2){ int fu=get(u1),fv=get(v1);w=read(); if(fu==fv) continue; g[u1].push_back(v1); g[v1].push_back(u1); add(u1,v1,w);add(v1,u1,w); f[fu]=fv; } } for(int i=1;i<=n;i++) if(!d[i]) dfs(i,0); for(int i=1;i<=t;i++){ int u1=ql[i].u1,v1=ql[i].v1,u2=ql[i].u2,v2=ql[i].v2,w=ql[i].w; int lc1=lca(u1,v1),lc2=lca(u2,v2);cnt++; build(lc1,u1,0,0);build(lc1,v1,0,0); build(lc2,u2,w,1);build(lc2,v2,w,1); } dijkstra();for(int i=1;i<=n;i++) printf("%d ",(dis[i]==0x3f3f3f3f)?-1:dis[i]); return 0; }
然后发现BZOJ4699具有90%的相似度，顺手a了，代码也不放了，读入改下就行了。
不过发现榜首的大爷们都是一个log的，orzorz