题目大意：给出n个点和m条边，其中n<=1e5,m-n<=20，q次询问，询问两点最短路。
题解：由于m-n<=20，所以可以当树上套环来做。先用最小生成树开一棵树，然后对于每个删掉的边的节点跑dij。
代码：
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 100050 #define ll long long ll n,m,q; struct node { ll u,c,v; }p[N]; bool cmp(node a,node b) { return a.v<b.v; } ll fa[N]; ll findfa(ll x) { if(fa[x]==x)return x; return fa[x] = findfa(fa[x]); } ll hed[N],cnt,hed2[N],cnt2; ll luk[N],dis[50][N],tk; struct EG { ll to,val,nxt; }e[2*N],e2[2*N]; void ae(ll f,ll t,ll v) { e[++cnt].to = t; e[cnt].val = v; e[cnt].nxt = hed[f]; hed[f] = cnt; } void ae2(ll f,ll t,ll v) { e2[++cnt2].to = t; e2[cnt2].val = v; e2[cnt2].nxt = hed2[f]; hed2[f] = cnt2; } ll dep[N],ds[N],ff[N],tp[N],siz[N],son[N]; void dfs1(ll u,ll f) { siz[u]=1; dep[u]=dep[f]+1; for(ll j=hed[u];j;j=e[j].nxt) { ll to = e[j].to; if(to==f)continue; ff[to]=u; ds[to]=ds[u]+e[j].val; dfs1(to,u); siz[u]+=siz[to]; if(siz[to]>siz[son[u]])son[u]=to; } } void dfs2(ll u,ll tu) { tp[u]=tu; if(!son[u])return ; dfs2(son[u],tu); for(ll j=hed[u];j;j=e[j].nxt) { ll to = e[j].to; if(to==ff[u]||to==son[u])continue; dfs2(to,to); } } ll get_lca(ll x,ll y) { while(tp[x]!=tp[y]) { if(dep[tp[x]]<dep[tp[y]])swap(x,y); x=ff[tp[x]]; } return dep[x]<dep[y]?x:y; } ll get_dis(ll x,ll y) { return ds[x]+ds[y]-2*ds[get_lca(x,y)]; } struct nd { ll x,d; nd(){} nd(ll x,ll d):x(x),d(d){} friend bool operator < (nd a,nd b) { return a.d>b.d; } }tpp; priority_queue<nd>que; bool vis[N]; void dij(ll x) { memset(vis,0,sizeof(vis)); dis[x][luk[x]]=0; que.push(nd(luk[x],0)); while(!que.empty()) { tpp = que.top(); que.pop(); ll u = tpp.x; if(vis[u])continue; vis[u]=1; for(ll j=hed2[u];j;j=e2[j].nxt) { ll to = e2[j].to; if(dis[x][to]>dis[x][u]+e2[j].val) { dis[x][to] = dis[x][u]+e2[j].val; que.push(nd(to,dis[x][to])); } } } } /*void fkstl() { int tmp[N]={-1,0},len=0; for(int i=1;i<=tk;i++) if(tmp[len]!=luk[i]) tmp[++len] = luk[i]; tk = len; for(int i=1;i<=tk;i++) luk[i]=tmp[i]; }*/ inline ll read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read(),m=read(); for(ll u,c,v,i=1;i<=m;i++) { u=read(),c=read(),v=read(); p[i].u=u,p[i].c=c,p[i].v=v; ae2(u,c,v),ae2(c,u,v); } sort(p+1,p+1+m,cmp); for(ll i=1;i<=n;i++)fa[i]=i; ll tot = 0; for(ll i=1;i<=m;i++) { ll u = p[i].u,c = p[i].c; ll f1 = findfa(u),f2 = findfa(c); if(f1!=f2) { ae(u,c,p[i].v);ae(c,u,p[i].v); fa[f1]=f2; tot++; }else { luk[++tk]=u; luk[++tk]=c; } } ll rt = findfa(1); dfs1(rt,0);dfs2(rt,rt); sort(luk+1,luk+1+tk); tk = unique(luk+1,luk+1+tk)-(luk+1); // fkstl(); memset(dis,0x7f,sizeof(dis)); for(ll i=1;i<=tk;i++) dij(i); q=read(); ll l,r; for(ll i=1;i<=q;i++) { l=read(),r=read(); ll ans = get_dis(l,r); for(ll j=1;j<=tk;j++) ans = min(ans,dis[j][l]+dis[j][r]); printf("%I64d ",ans); } return 0; }