解题思路：
先用BFS预处理出每个字母节点到其它节点的最短路径，然后套用prime算法。
#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <algorithm>#include <queue>#include <stack>#include <vector>#include <set>#include <map>#define LL long long using namespace std;const int MAXN = 100 + 10;char G[MAXN][MAXN];int A[MAXN][MAXN];int N, M;int g[][2] = {{-1,0},{1,0},{0,-1},{0,1}};int cost[MAXN][MAXN];int t[MAXN][MAXN];void bfs(int sx, int sy){memset(t, -1, sizeof(t));queue<pair<int,int> > Q;Q.push(make_pair(sx,sy));t[sx][sy] = 0;while(!Q.empty()){pair<int,int> u = Q.front();Q.pop();if(A[u.first][u.second] != -1){cost[A[sx][sy]][A[u.first][u.second]] = t[u.first][u.second];}for(int i=0;i<4;i++){int x = u.first + g[i][0];int y = u.second + g[i][1];if(G[x][y] == '#' || t[x][y] != -1)continue;t[x][y] = t[u.first][u.second] + 1;Q.push(make_pair(x,y));}}}const int INF = 0x3f3f3f3f;bool vis[MAXN];int lowc[MAXN];int prime(int n){int ans = 0;memset(vis, 0, sizeof(vis));vis[0] = true;for(int i=1;i<n;i++) lowc[i] = cost[0][i];for(int i=1;i<n;i++){int minc = INF;int p = -1;for(int j=0;j<n;j++){if(!vis[j] && minc > lowc[j]){minc = lowc[j];p = j;}}if(minc == INF) return -1;ans += minc;vis[p] = true;for(int j=0;j<n;j++){if(!vis[j] && lowc[j] > cost[p][j])lowc[j] = cost[p][j];}}return ans;}int main(){int T;scanf("%d", &T);while(T–){scanf("%d%d", &M, &N);gets(G[0]);int tot = 0;for(int i=0;i<N;i++)gets(G[i]);/*for(int i=0;i<N;i++){for(int j=0;j<M;j++)cout<<G[i][j];cout<<endl;}*/memset(A, -1, sizeof(A));for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(G[i][j] == 'S' || G[i][j] == 'A')A[i][j] = tot++;}}for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(A[i][j] != -1)bfs(i, j);}}int ans = prime(tot);printf("%d\n", ans);}return 0;}
，都在努力为你驱逐烦恼焦躁，
