首页 技术 正文
技术 2022年11月23日
0 收藏 847 点赞 4,150 浏览 1735 个字

题目链接:

https://vjudge.net/contest/66965

具体思路:

首先将每个点之间的最短距离求出(bfs),A 或者 S作为起点跑bfs,这样最短距离就求出来了。然后再用最短路的算法求出最小生成树的权值的和就可以了,getchar的注意事项在代码中解释。

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stdio.h>
using namespace std;
# define maxn 1000+10
# define inf 0x3f3f3f3f
# define ll long long
int n,m,num;
char a[maxn][maxn];
int vis[maxn][maxn];
int dis[maxn][maxn];
int f[2][4]= {{1,-1,0,0},{0,0,1,-1}};
int p[maxn];
int t[maxn][maxn];
int vis1[maxn*maxn];
struct node
{
int x,y,step;
node() {}
node(int xx,int yy,int zz)
{
x=xx;
y=yy;
step=zz;
}
};
bool judge(int t1,int t2)
{
if(t1>=0&&t1<n&&t2>=0&&t2<m)return true;
return false;
}
void bfs(int t1,int t2)
{
queue<node>q;
while(!q.empty())q.pop();
memset(vis,0,sizeof(vis));
vis[t1][t2]=1;
q.push(node(t1,t2,0));
while(!q.empty())
{
node temp=q.front();
q.pop();
if(t[temp.x][temp.y])
{
dis[t[t1][t2]][t[temp.x][temp.y]]=dis[t[temp.x][temp.y]][t[t1][t2]]=temp.step;
}
for(int i=0; i<4; i++)
{
int x=temp.x+f[0][i];
int y=temp.y+f[1][i];
if(judge(x,y)&&vis[x][y]==0&&a[x][y]!='#')
{
vis[x][y]=1;
q.push(node(x,y,temp.step+1));
}
}
}
}
int prim()
{
memset(vis1,0,sizeof(vis1));
int sum=0;
for(int i=1; i<=num; i++)
{
p[i]=dis[1][i];
}
vis1[1]=1;
for(int j=2; j<=num; j++)
{
int minn=inf,po;
for(int i=1; i<=num; i++)
{
if(!vis1[i]&&p[i]<minn)
{
minn=p[i];
po=i;
}
}
vis1[po]=1;
sum+=minn;
for(int i=1; i<=num; i++)
{
if(!vis1[i]&&dis[po][i]<p[i])
{
p[i]=dis[po][i];
}
}
}
return sum;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
num=0;
memset(t,0,sizeof(t));
scanf("%d %d",&m,&n);
gets(a[0]);//这里要先输入a[0]的原因是二维数组输入的时候会将回车也当成一个字符输入,所以二维数组的最后一行存储不上。
for(int i=0; i<n; i++)
{
gets(a[i]);
for(int j=0; j<m; j++)
{
if(a[i][j]=='S'||a[i][j]=='A')
{
num++;
t[i][j]=num;
}
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(t[i][j]==0)continue;
bfs(i,j);
}
}
int ans=prim();
// printf("%d\n",ans);
}
return 0;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,254
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,692
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,531
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,302
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,942
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,102