图论好题啊！
首先我们枚举终点 \(u\)，看到一定要走完指定的 \(m\) 条边，很像一条欧拉路问题啊！但是现在问题是一个欧拉路问题，有两个点的度数是奇数，并不好做。我们不妨先从起点 \(s\) 向 \(u\) 连一条边，变成欧拉回路问题。现在我们需要做的是将度数为奇数的点加边使其变为偶数。方法是将连续两个度数为奇数的点，中间的任意相邻两点连上一条度数为 \(1\) 的边。因为这样不但连通了更多的节点，代价还和直接连接两点的代价相同，肯定更优。
现在我们的图变成了若干个连通块了，想要使得图连通，我们需要在连通块之间找一条边，让它变成一张连通图，实际上就是一个最小生成树。我们先将连通块缩点，拿相邻的两个点连边，跑一个最小生成树即可。时间复杂度 \(O(n^2 \log n+m)\)。
点击查看代码
#include<bits/stdc++.h>
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();
#define ll long long
#define i128 __int128
using namespace std;
inline int read() {
int xx= 0;int f= 1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-') f= -1;
c= getchar();
}
while(c>='0'&&c<='9') {
xx= (xx<<1)+(xx<<3)+(c^48);
c= getchar();
}
return xx*f;
}
#define maxn 200050
int n,m,st;
int deg[maxn];
int res;
int fa[maxn],bel[maxn];
struct node {
int u,v,d;
bool operator<(const node x) {return d<x.d; }
};
int find(int x) {return x==fa[x]?fa[x]:fa[x]=find(fa[x]); }
signed main() {
in3(n,m,st);
For(i,1,n) fa[i]=i;
For(i,1,m) {
int u,v;
in2(u,v);
deg[u]++,deg[v]++;
res+=abs(u-v);
fa[find(u)]=find(v);
}
For(i,1,n) bel[i]=find(i);//先缩一次点
For(u,1,n) {
deg[st]++,deg[u]++;
For(i,1,n) fa[i]=i;
fa[find(st)]=find(u);
int ans=res,lst=0;
For(i,1,n) if(deg[i]%2==1) {
if(lst) {ans+=i-lst; For(j,lst,i) fa[find(bel[j])]=find(bel[i]); lst=0; }
else lst=i;
}
vector<node>G; lst=0;
For(i,1,n) if(deg[i]>0) {
if(lst&&find(bel[lst])!=find(bel[i]))
G.push_back({bel[lst],bel[i],abs(i-lst)});
lst=i;
}
sort(G.begin(),G.end());
for(auto [x,y,z]:G)
if(find(x)!=find(y))
fa[find(x)]=find(y),ans+=2*z;
cout<<ans<<' ';
deg[u]--,deg[st]--;
}
}