首先有两个前置技巧：1) 两点间的最短距离就是直接连接两点的边的长度；2) 遍历一个子图的最小花费是最小生成树的边权之和乘二。原问题让我们找出一条最短且必经过钦定边的 \(( s, i )\) 路径，那么我们先将 \(\lang s , i \rang\) 连上，问题就变成了找出一条最短且必经过钦定边 \(( s, i)\) 的回路。虽然每条边不一定恰好经过一次，但是对于正确性的判断，每个点的度数为偶数依然是一个必要条件，再加上连通性的限制，一条回路的正确性就可以由这两条必要条件充要表示。
其次来考虑如何修复每个点度数的奇偶性，一个贪心策略是把一条 \((s, i)\) 拆成 \((s, s+1), (s+1, s+2) \dots (i-1, i)\)，由于边权的性质，可以发现这样拆分一定不劣；又考虑连通性修复，类似以上。
const int MN = 2.5e3;
int n, m, s, fa[MN + 100], deg[MN + 100];
int find(int u) {
while (u != fa[u]) u = fa[u] = fa[fa[u]];
return u;
}
bool unite(int u, int v) {
if (find(u) != find(v)) {fa[find(u)] = find(v);return 1;}
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(nullptr);
cin >> n >> m >> s; s --;
iota(fa, fa+n, 0);
ll res = 0;
rep(m) {
int u, v;cin >> u >> v;u--;v--;
deg[u] ++ , deg[v] ++;
res += abs(u - v);
unite(u, v);
}
vi tmp(fa, fa+n);
rep(n) {
deg[s] ++ , deg[i] ++;
unite(s, i);
vi id;
rep(j,n) if (deg[j]%2) id.pb(j);
ll sum = 0;
rep(j,intsz(id)-1) {
rep(k,id[j],id[j+1]) unite(k, k+1);
sum += id[j+1]-id[j];
j++;
}
vi from, to; vi().swap(id);
rep(j,n) if (deg[j] > 0) id.pb(j);
rep(j,intsz(id)-1) from.pb(id[j]), to.pb(id[j+1]);
vi(intsz(to)).swap(id);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y) {
return to[x]-from[x]<to[y]-from[y];
});
for (int j : id) {
if (unite(from[j], to[j])) sum += 2*(to[j]-from[j]);
}
cout<< res + sum << " \n"[i==n-1];
deg[s] -- , deg[i] --;
rep(j,n) fa[j] = tmp[j];
}
}
/*
急
|
|
速
|
|
地
|
|
下
|
|
坠
|
|
*/