CF1051F The Shortest Statement 题解

题意

给一张\(n\) 个点\(m\) 条边的无向连通图。有\(q\) 次询问，给出两个点，求问两个点间的最短路长度。

思路

既然都是思维题了，那本题正解思路和我的想法必然不搭边了。好像除了暴力跑就没辙了......吗？

注意到题上有个很诡异的条件\(m-n<=20\)。思考为什么要放如此诡异的一个条件。如果学过基环树，相信很快就能出思路，很可惜我没学过。在题解区遨游完一轮可以发现，如果先将原图建成一棵树，这个诡异条件最多就涉及42个点。既然建出树了那树上距离可以\(O(1)\) 求。而且一条路径经过的无非就是树上的边和诡异的边，所以可以先建出原图，并建出原图的生成树，再对于没有在树上的诡异边的两个端点跑原图的最短路。询问时就\(O(1)\) 求树上的距离和以某条诡异边的诡异端点为中转点的最短路，取最小值输出就行了。时间上是显然能过的，因为瓶颈就在于\(O(nlogn)\) 的求最短路，求最短路和询问都只有一个最大为42的常数，故可以通过此题。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
typedef pair<int,int> pii;
int n,m;
int tot,to[maxn<<1],nxt[maxn<<1],h[maxn<<1],val[maxn<<1];
inline void adde(int x,int y,int z){to[++tot]=y;nxt[tot]=h[x];h[x]=tot;val[tot]=z;
}
int k[maxn],sum;
bool insta[maxn];
int dis[50][maxn];
priority_queue<pii> q;
bool vis[maxn];
inline void dij(int x,int pos){memset(dis[pos],0x3f,sizeof(dis[pos]));memset(vis,0,sizeof(vis));dis[pos][x]=0;q.push({0,x});while(q.size()){int u=q.top().second;q.pop();if(vis[u]) continue;vis[u]=1;for(int i=h[u];i;i=nxt[i]){int y=to[i];if(dis[pos][y]>dis[pos][u]+val[i]){dis[pos][y]=dis[pos][u]+val[i];q.push({-dis[pos][y],y});}}}
}
struct tree{int dep[maxn],siz[maxn],son[maxn],fa[maxn],dis[maxn];int tot,to[maxn<<1],nxt[maxn<<1],h[maxn<<1],val[maxn<<1];int top[maxn];int papa[maxn];tree(){tot=dis[1]=dep[0]=0;memset(h,0,sizeof(h));}inline int getfa(int x){if(x==papa[x]) return x;papa[x]=getfa(papa[x]);return papa[x];}inline void merge(int x,int y){x=getfa(x),y=getfa(y);if(x!=y) papa[x]=y;}inline void adde(int x,int y,int z){to[++tot]=y;nxt[tot]=h[x];h[x]=tot;val[tot]=z;}inline void dfs1(int x,int f){siz[x]=1;son[x]=0;dep[x]=dep[f]+1;fa[x]=f;for(int i=h[x];i;i=nxt[i]){int y=to[i];if(y==f) continue;dis[y]=dis[x]+val[i];dfs1(y,x);siz[x]+=siz[y];if(siz[y]>siz[son[x]]) son[x]=y;}}inline void dfs2(int x,int t){top[x]=t;if(!son[x]) return;dfs2(son[x],t);for(int i=h[x];i;i=nxt[i]){int y=to[i];if(y==fa[x]||y==son[x]) continue;dfs2(y,y);}}inline int lca(int a,int b){while(top[a]!=top[b]){if(dep[top[a]]<dep[top[b]]) swap(a,b);a=fa[top[a]];}if(dep[a]<dep[b]) return a;return b;}inline int getdis(int a,int b){return dis[a]+dis[b]-2*dis[lca(a,b)];}
}lca;
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) lca.papa[i]=i;for(int i=1,u,v,d;i<=m;i++){cin>>u>>v>>d;adde(u,v,d);adde(v,u,d);if(lca.getfa(u)!=lca.getfa(v)) lca.adde(u,v,d),lca.adde(v,u,d),lca.merge(u,v);else{if(!insta[u]) insta[u]=1,k[++sum]=u;if(!insta[v]) insta[v]=1,k[++sum]=v;}}for(int i=1;i<=sum;i++) dij(k[i],i);lca.dfs1(1,0);lca.dfs2(1,1);int qq;cin>>qq;for(int i=1,u,v;i<=qq;i++){cin>>u>>v;int ans=lca.getdis(u,v);for(int j=1;j<=sum;j++) ans=min(ans,dis[j][u]+dis[j][v]);cout<<ans<<'\n';}return 0;
}