模拟退火。

对于每一组 $(k_i,k_j)$，计算出从 $k_i$ 到达 $k_j$ 的距离 $dis_{i,j}$。再对于每一个 $k_i$ 计算出从其到达中转站的距离 $d_i$。注意对于每一个 $k_i$，完成上述计算只需要一次 BFS，否则会 MLE。

接着模拟退火，将点两两匹配，注意到两次两次送一定是不劣的。 ::::success[证明]{open} 设这两个不同的点为 $i$ 和 $j$。

一起送的花费为：$d_i+dis_{i,j}+d_j$，分开送的花费为 $2 \times (d_i+d_j)$，则它们的花费差为 $dis_{i,j}-d_i-d_j$。显然有 $dis_{i,j} \leq d_i+d_j$，当且仅当中转站位于 $i$ 和 $j$ 的最短路径上时取等。即两次两次送一定不劣。 :::: 有一个小细节：每次交换后最短时间不用重新计算，只需保存上次计算的值，修改交换的两个点的贡献即可 $O(1)$ 计算。

代码实现几乎没有难度，如果 WA 了可以试着多交几遍或者改改模拟退火参数。

通过记录
::::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=5e2+5,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},INF=1e6;
struct P
{
	int x,y;
	friend bool operator ==(P a,P b) {return a.x==b.x&&a.y==b.y;}
}p[N];
int n,m,k,dis[N][N],b[N][N],d[N],r[N],sx,sy,l,ans=INF;
double StartT=3e3,EndT=1e-9,DeltaT=0.996;
char a[N][N];
bool vis[N][N];
queue <pair<P,int> > q;
mt19937 rnd(time(0));
void Bfs(P s,int id)
{
	memset(vis,0,sizeof(vis));
	while(q.size()) q.pop();
	q.push(make_pair(s,0));
	vis[s.x][s.y]=1;
	while(q.size())
	{
		int x=q.front().first.x,y=q.front().first.y,s=q.front().second;
		if(x==sx&&y==sy) d[id]=s;
		if(a[x][y]=='X') dis[id][b[x][y]]=dis[b[x][y]][id]=s;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx>0&&tx<=n&&ty>0&&ty<=m&&a[tx][ty]!='#'&&vis[tx][ty]==0)
				vis[tx][ty]=1,q.push(make_pair((P){tx,ty},s+1));
		}
	}
}
int F(int x)
{
	if((k&1)&&x==k) return d[r[k]]*2;
	if(x>k/2) x=x-k/2;
	return d[r[x]]+dis[r[x]][r[k/2+x]]+d[r[k/2+x]];
}
void SA()
{
	int now=INF,lst=0;
	shuffle(r+1,r+k+1,rnd);
	for(int i=1;i<=k/2;i++) lst+=F(i);
	if(k&1) lst+=F(k);
	for(double T=StartT;T>EndT;T*=DeltaT)
	{
		int x=rnd()%k+1,y=rnd()%k+1,t=lst;
		t-=F(x),t-=F(y);
		swap(r[x],r[y]);
		t+=F(x),t+=F(y);
		if(t<now) now=t,lst=t;
		else if(exp((now-t)/T)<1.0*rnd()/rnd.max()) swap(r[x],r[y]);
		else lst=t;
	}
 	ans=min(ans,now);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='X') p[++l]={i,j},b[i][j]=l;
			if(a[i][j]=='S') sx=i,sy=j;
		}
	for(int i=1;i<=k;i++)
	{
		d[i]=INF;r[i]=i;
		for(int j=1;j<=k;j++) dis[i][j]=INF;
	}		
	for(int i=1;i<=k;i++) Bfs(p[i],i);
	while(1.0*clock()/CLOCKS_PER_SEC<=0.99) SA();
	if(ans>=INF) cout<<"-1\n";
	else cout<<ans<<"\n";
	return 0;
}

::::