题意：给定一个10W的无向联通图，和10W的询问，每个询问求任意两点间的距离，限制条件是边数-点数不超过20
一般来说图上任意两点间的距离都会采用Floyd算法直接做，但是这个数据范围显然是不合理的，好在给了我们一个限制条件。
我们先考虑，如果边数是点数N - 1，这就变成了一颗N结点的树，两点间的距离可以用ln的时间复杂度用LCA的算法求出，在本题中加上了20条额外的边，事实上我们单独考虑每个边对于最短路的贡献，也就是原本走lca路线的边走这些边是不是会快一些，
有了这个想法，我们可以将树上的路径看作大路，也就是正常走的路径，加上的额外的边看作通道，对于每一次询问，只要考虑走通道是否能实现更优的路径即可。
所以整体的思路就变成了LCA求正常路径（中途顺手求了一个重心作为根节点），然后floyd预处理通道之间的关系，询问的时候就是40 * 40 * Q的时间复杂度输出。
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d ", x) #define Prl(x) printf("%lld ",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second inline LL read(){LL now=0;register char c=getchar();for(;!isdigit(c);c=getchar()); for(;isdigit(c);now=now*10+c-'0',c=getchar());return now;} typedef vector<int> VI; const double eps = 1e-9; const int maxn = 1e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int fa[maxn]; struct Edge{ int to,next; LL dis; }edge[maxn * 2]; struct Edge2{ int u,v; LL w; Edge2(int u = 0,int v = 0 ,LL w = 0):u(u),v(v),w(w) {} }E[maxn]; int head[maxn],tot; void init(){ for(int i = 1; i <= N ; i ++){ fa[i] = i; head[i] = -1; } tot = 0; } void add(int u,int v,LL w){ edge[tot].to = v; edge[tot].dis = w; edge[tot].next = head[u]; head[u] = tot++; } int find(int p){ return p == fa[p]?p:fa[p] = find(fa[p]); } void Union(int a,int b){ a = find(a); b = find(b); fa[a] = b; } int v[maxn],size[maxn],root,ans; void dfsroot(int x){ v[x] = 1,size[x] = 1; int max_part = 0; for(int i = head[x] ; ~i ; i = edge[i].next){ int y = edge[i].to; if(v[y]) continue; dfsroot(y); size[x] += size[y]; max_part = max(max_part,size[y]); } max_part = max(max_part,N - size[x]); if(max_part < ans){ ans = max_part; root = x; } } const int SP = 20; int pa[maxn][SP],dep[maxn]; LL dis[maxn]; void dfs(int u,int fa){ pa[u][0] = fa; dep[u] = dep[fa] + 1; for(int i = 1; i < SP ; i ++) pa[u][i] = pa[pa[u][i - 1]][i - 1]; for(int i = head[u]; ~i ;i = edge[i].next){ int v = edge[i].to; if(v == fa) continue; dis[v] = dis[u] + edge[i].dis; dfs(v,u); } } int lca(int u,int v){ if(dep[u] < dep[v]) swap(u,v); int t = dep[u] - dep[v]; for(int i = 0 ; i < SP; i ++) if(t & (1 << i)) u = pa[u][i]; for(int i = SP - 1; i >= 0 ; i --){ int uu = pa[u][i],vv = pa[v][i]; if(uu != vv){ u = uu; v = vv; } } return u == v?u:pa[u][0]; } LL DIS(int u,int v){return dis[u] + dis[v] - 2 * dis[lca(u,v)];} LL D[maxn]; int vis[maxn]; int flag[maxn]; LL MAP[50][50]; LL INIT[maxn][50]; int main() { Sca2(N,M); init(); int cnt = 0,num = 0; for(int i = 1; i <= M ; i ++){ int u = read(); int v = read(); LL w = read(); if(find(u) == find(v)){ E[++cnt] = Edge2(u,v,w); if(!vis[u]){flag[++num] = u;vis[u] = num;} if(!vis[v]){flag[++num] = v;vis[v] = num;} }else{ add(u,v,w); add(v,u,w); Union(u,v); } } root = 1;ans = INF; dfsroot(1); dis[root] = 0; dfs(root,-1); for(int i = 1; i <= num ; i ++) for(int j = 1; j <= num ; j ++) MAP[i][j] = DIS(flag[i],flag[j]); for(int i = 1; i <= cnt;i ++) MAP[vis[E[i].v]][vis[E[i].u]] = MAP[vis[E[i].u]][vis[E[i].v]] = min(MAP[vis[E[i].u]][vis[E[i].v]],E[i].w); for(int k = 1; k <= num ; k ++) for(int i = 1; i <= num ; i ++) for(int j = 1; j <= num ; j ++) MAP[i][j] = min(MAP[i][j],MAP[i][k] + MAP[k][j]); for(int i = 1; i <= N ; i ++) for(int j = 1; j <= num; j ++) INIT[i][j] = DIS(i,flag[j]); int q = read(); while(q--){ int u= read();int v = read(); LL ANS = DIS(u,v); for(int i = 1; i <= num; i ++){ for(int j = 1; j <= num ; j ++){ ANS = min(ANS,INIT[u][i] + MAP[i][j] + INIT[v][j]); } } Prl(ANS); } #ifdef VSCode system("pause"); #endif return 0; }