http://blog.csdn.net/lyy289065406/article/details/6645991题目翻译的很好，反正我是看不懂题目
#include <iostream>#include <cstdio>#include <utility>#include <algorithm>#include <queue>#include <cstring>using namespace std;char g[100][100];int n,m;int a[100][100];int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};int cost[110][110];int t[100][100];void bfs(int sx, int sy){ queue<pair<int, int> > q; while(!q.empty()) q.pop(); memset(t,-1,sizeof(t)); t[sx][sy] = 0; q.push(make_pair(sx,sy)); while(!q.empty()) { pair<int, int> now = q.front(); q.pop(); if(a[now.first][now.second] != -1) cost[a[sx][sy]][a[now.first][now.second]] = t[now.first][now.second]; for(int i = 0; i < 4; ++i) { int tx = now.first + dir[i][0]; int ty = now.second + dir[i][1]; if(g[tx][ty] == '#' || t[tx][ty] != -1) continue; t[tx][ty] = t[now.first][now.second] + 1; q.push(make_pair(tx,ty)); } }}const int INF = 99999999;int book[110];int dis[110];int PRim(int n){ int res = 0; memset(book,0,sizeof(book)); book[0] = 1; for(int i = 0; i < n; ++i) dis[i] = cost[0][i]; int cnt = 1,minn = INF,t; while(cnt < n) { minn = INF; for(int i = 0; i < n; ++i) { if(book[i] == 0 && minn > dis[i]) { minn = dis[i]; t = i; } } book[t] = 1; cnt++; res += dis[t]; for(int i = 0; i < n; ++i) { if(book[i] == 0 && dis[i] > cost[t][i]) dis[i] = cost[t][i]; } } return res;}int main(){ int t; scanf("%d",&t); while(t--) { //后边的/n是用来吃掉换行符的，很纳闷用getchar()竟然会wa scanf("%d %d/n",&m,&n); memset(a,-1,sizeof(a)); int tol = 0; for(int i = 0; i < n; ++i) { gets(g[i]); for(int j = 0; j < m; ++j) { if(g[i][j] == 'A' || g[i][j] == 'S') a[i][j] = tol++; } } for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(a[i][j] != -1) bfs(i,j); printf("%d/n",prim(tol)); } return 0;}新闻热点
疑难解答
