题目说从S开始，在S或者A的地方可以分裂前进。 想一想后发现就是求一颗最小生成树。
首先bfs预处理得到每两点之间的距离，我的程序用map做了一个映射，将每个点的坐标映射到1-n上，这样建图比较方便。
然后一遍prime就够了。注意用gets（）读入地图的时候，上面还要用一个gets（）接住无用的空格。。（为啥不用getchar？0 0，看了讨论版才知道，
因为空格很多………………）
#include #include #include #include #include using namespace std; #define INF 0x3f3f3f3f char map1[55][55]; int head,tail; int x,y; map M; struct node { int x,y; int dis; }q[100000]; int top; int start; int dx[]={-1,1,0,0}; int dy[]={0,0,-1,1}; int dis[150][150]; bool vis[150][150]; void bfs(int k,int st) { memset(vis,0,sizeof(vis)); head=tail=0; node tmp,tt; tmp.x=st/x; tmp.y=st%x; vis[tmp.x][tmp.y]=1; tmp.dis=0; int tot=0; q[tail++]=tmp; int f; while(headd[j]) { min=d[j]; v=j; } } sum+=min; visit[v]=1; for(j=1;j<=n;j++) { if(!visit[j]&&dis[v][j]