RT

感觉写的没啥问题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,m,q;
ll x,y,z;
struct edge{
	ll u,v,w,nxt;
}e[MAXN],tree[MAXN];
ll head[MAXN],edge_num;
void add_edge(ll From,ll To,ll Len){
	e[++edge_num]=(edge){From,To,Len,head[From]};
	head[From]=edge_num;
	return;
}
ll head_tree[MAXN],tree_num;
void add_tree(ll From,ll To,ll Len){
	tree[++tree_num]=(edge){From,To,Len,head_tree[From]};
	head_tree[From]=tree_num;
	return;
}
ll dfn[MAXN],low[MAXN],cnt,st[MAXN],top;
ll tot;
void tarjan(ll now,ll father){
	dfn[now]=low[now]=++cnt;
	st[++top]=now;
	for(int i=head[now];i;i=e[i].nxt){
		if(!dfn[e[i].v]){
			tarjan(e[i].v,now);
			low[now]=min(low[now],low[e[i].v]);
			if(low[e[i].v]>=dfn[now]){
				tot++;
				while(st[top+1]!=e[i].v){
					add_tree(tot,st[top],0);
					add_tree(st[top],tot,0);
					top--;
				}
				add_tree(tot,st[top],0);
				add_tree(st[top],tot,0);
			}
		}
		else if(e[i].v!=father)low[now]=min(low[now],dfn[e[i].v]);
	}
	return;
}
ll deep[MAXN],fa[MAXN][35];
void pre(ll now,ll father){
	for(int i=1;i<=30;i++)fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head_tree[now];i;i=tree[i].nxt){
		if(tree[i].v==father)continue;
		deep[tree[i].v]=deep[now]+1;
		fa[tree[i].v][0]=now;
		pre(tree[i].v,now);
	}
	return;
}
ll dis_on_ring[MAXN],sum[MAXN];
bool on_ring[MAXN];
bool vis[MAXN];
void pre_square(ll now){
	ll qwq=0;
	for(int i=head_tree[now];i;i=tree[i].nxt)on_ring[tree[i].v]=1,qwq++;
	ll st=fa[now][0];
	if(qwq==2){
		ll _end=0,tmp=0;
		for(int i=head_tree[now];i;i=tree[i].nxt)if(tree[i].v!=st)_end=tree[i].v;
		for(int i=head[st];i;i=e[i].nxt){
			if(e[i].v==_end){
				tmp++;
				sum[now]+=e[i].w;
				dis_on_ring[_end]=e[i].w;
			}
		}
		if(tmp==1)sum[now]<<=1;
		for(int i=head_tree[now];i;i=tree[i].nxt)if(tree[i].v==_end)tree[i].w=min(dis_on_ring[_end],sum[now]-dis_on_ring[_end]);
		for(int i=head_tree[now];i;i=tree[i].nxt)on_ring[tree[i].v]=0;
		return;
	}
	ll now_p=st,nxt=0,now_len=0;
	while(1){
		vis[now_p]=1;
		for(int i=head[now_p];i;i=e[i].nxt){
			if(vis[e[i].v]||(on_ring[e[i].v]==0))continue;
			nxt=e[i].v;
			now_len+=e[i].w;
			break;
		}
		if(nxt==0||nxt==now_p)break;
		dis_on_ring[nxt]=now_len;
		sum[now]=now_len;
		now_p=nxt;
	}
	for(int i=head[now_p];i;i=e[i].nxt)if(e[i].v==st){
		sum[now]+=e[i].w;
		break;
	}
	for(int i=head_tree[now];i;i=tree[i].nxt){
		if(tree[i].v==st)continue;
		tree[i].w=min(dis_on_ring[tree[i].v],sum[now]-dis_on_ring[tree[i].v]);
	}
	for(int i=head_tree[now];i;i=tree[i].nxt)on_ring[tree[i].v]=vis[tree[i].v]=0;
	return;
}
ll dis[MAXN];
void get_dis(ll now,ll father){
//	cout<<"now "<<now<<endl;
	for(int i=head_tree[now];i;i=tree[i].nxt){
		if(tree[i].v==father)continue;
		dis[tree[i].v]=dis[now]+tree[i].w;
		get_dis(tree[i].v,now);
	}
	return;
}
ll solve(ll X,ll Y){
	if(deep[X]<deep[Y])swap(X,Y);
	for(int i=30;i>=0;i--)if(deep[fa[X][i]]>=deep[Y])X=fa[X][i];
	for(int i=30;i>=0;i--)if(fa[X][i]!=fa[Y][i])X=fa[X][i],Y=fa[Y][i];
	if(fa[X][0]<=n)return dis[x]+dis[y]-2*dis[fa[X][0]];
	else{
		if(dis_on_ring[X]<dis_on_ring[Y])swap(X,Y);
		ll LEN=min(dis_on_ring[X]-dis_on_ring[Y],sum[fa[X][0]]-dis_on_ring[X]+dis_on_ring[Y]);
		return dis[x]+dis[Y]-dis[X]-dis[Y]+LEN;
	}
}
int main(){
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		if(x==y)continue;
		add_edge(x,y,z);
		add_edge(y,x,z); 
	}
	tot=n;
	tarjan(1,0);
//	cout<<endl;
//	for(int i=1;i<=tree_num;i++)cout<<tree[i].u<<" "<<tree[i].v<<endl;
	pre(1,0);
	for(int i=n+1;i<=tot;i++)pre_square(i);
//	cout<<endl;
//	for(int i=1;i<=tree_num;i++)cout<<tree[i].u<<" "<<tree[i].v<<" "<<tree[i].w<<endl;
	get_dis(1,0);
//	cout<<"?\n";
	for(int i=1;i<=q;i++){
		cin>>x>>y;
		cout<<solve(x,y)<<'\n';
	}
	return 0;
}