题解 CF1051F【The Shortest Statement】

problem

连通图，无自环，无重边，\(m-n\leq 20\)，\(n\leq 10^5\)，\(10^5\) 询问两点之间最短路。

solution

搞出任意一棵生成树。一共 \(21\) 条非树边。

对于任意一条路径，它只有如下 \(22\) 种情况：

• 不经过非树边。
• 经过第 \(i\) 条非树边（\(1\leq i\leq 21\)）。

这里我们不用枚举非树边的子集之类的东西，一是不好做，二是这是最优性问题，每个元素的方案的并就是全集。

对于不经过非树边的，【模板】树上两点带权距离。

对于经过一条非树边的，从边的一端开始跑最短路即可。

最后的答案为以上 \(22\) 种情况的 \(\min\)。复杂度 \(O(mk\log m+q(\log n+k))\) 其中 \(k=m-n\)。

code

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template<int N> struct dsu{
	int fa[N+10],siz[N+10],cnt;
	dsu(int n=N):cnt(n){for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;}
	int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	void merge(int x,int y){if(x=find(x),y=find(y),x!=y) cnt--,siz[x]<siz[y]&&(swap(x,y),0),siz[fa[y]=x]+=siz[y];}
};
template<int N,int M,class T=int> struct graph{
    int head[N+10],nxt[M*2+10],cnt;
    struct edge{
        int u,v;T w;
        edge(int u=0,int v=0,T w=0):u(u),v(v),w(w){}
    } e[M*2+10];
    graph(){memset(head,cnt=0,sizeof head);}
    edge&operator[](int i){return e[i];}
    int add(int u,int v,T w=0){return e[++cnt]=edge(u,v,w),nxt[cnt]=head[u],head[u]=cnt;}
    int link(int u,int v,T w=0){return add(u,v,w),add(v,u,w);}
};
template<int N,int M,class T=int> struct shortway: public graph<N,M,T>{
    graph<N,M,T> &g=*this;
	bool vis[N+10];
	void dijkstra(int s,LL dis[]){
		memset(vis,0,sizeof vis);
		priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>> q;
		for(q.push({dis[s]=0,s});!q.empty();){
			int u=q.top().second; q.pop();
			if(vis[u]) continue; else vis[u]=1;
			for(int i=g.head[u];i;i=g.nxt[i]){
				int v=g[i].v;
				if(dis[v]>dis[u]+g[i].w) q.push({dis[v]=dis[u]+g[i].w,v});
			}
		}
	}
};
template<int N,int M,class T=int> struct treecut: public graph<N,M,T>{
    graph<N,M,T> &g=*this;
    int fa[N+10],dep[N+10],son[N+10],siz[N+10],
        dfn[N+10],rnk[N+10],top[N+10],cnt;
    treecut(){memset(son,cnt=siz[0]=0,sizeof son);}
    void dfs(int u,int f=0){
        dep[u]=dep[fa[u]=f]+1,siz[u]=1;
        for(int i=g.head[u];i;i=g.nxt[i]){
            int v=g[i].v; if(v==fa[u]) continue;
            dfs(v,u),siz[u]+=siz[v];
            if(siz[son[u]]<siz[v]) son[u]=v;
        }
    }
    void cut(int u,int topf){
        top[rnk[dfn[u]=++cnt]=u]=topf;
        if(son[u]) cut(son[u],topf);
        for(int i=g.head[u];i;i=g.nxt[i]){
            int v=g[i].v; if(v==fa[u]||v==son[u]) continue;
            cut(v,v);
        }
    }
    int lca(int u,int v){
        for(;top[u]!=top[v];u=fa[top[u]]) if(dep[top[u]]<dep[top[v]]) swap(u,v);
        if(dep[u]<dep[v]) swap(u,v); return v;
    }
};
int n,m,q,pos[30],cnt;
LL dis[30][100010],sum[100010];
shortway<100010,100100> g;
treecut<100010,100010> t;
dsu<100010> s;
void dfs(int u){for(int i=t.head[u];i;i=t.nxt[i]) if(t[i].v!=t.fa[u]) sum[g[i].v]=sum[u]+g[i].w,dfs(t[i].v);}
int main(){
//	#ifdef LOCAL
//	 	freopen("input.in","r",stdin);
//	#endif
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		pos[++cnt]=g.link(u,v,w);
		if(s.find(u)!=s.find(v)) cnt--,t.link(u,v,w),s.merge(u,v);
	}
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=cnt;i++) g.dijkstra(g[pos[i]].u,dis[i]);
	t.dfs(1),t.cut(1,1),dfs(1);
	scanf("%d",&q);
	for(int i=1,u,v;i<=q;i++){
		scanf("%d%d",&u,&v);
		LL ans=sum[u]+sum[v]-2*sum[t.lca(u,v)];
		for(int j=1;j<=cnt;j++) ans=min(ans,dis[j][u]+dis[j][v]);
		printf("%lld\n",ans);
	}
	return 0;
}  

原文地址：http://www.cnblogs.com/caijianhong/p/solution-CF1051F.html