首页 > 代码库 > 街区最短路径问题
街区最短路径问题
描述
一个街区有很多住户，街区的街道只能为东西、南北两种方向。
住户只可以沿着街道行走。
各个街道之间的间隔相等。
用(x,y)来表示住户坐在的街区。
例如（4,20），表示用户在东西方向第4个街道，南北方向第20个街道。
现在要建一个邮局，使得各个住户到邮局的距离之和最少。
求现在这个邮局应该建在那个地方使得所有住户距离之和最小；
- 输入
- 第一行一个整数n<20，表示有n组测试数据，下面是n组数据;
- 每组第一行一个整数m<20,表示本组有m个住户，下面的m行每行有两个整数0<x,y<100，表示某个用户所在街区的坐标。
- m行后是新一组的数据；
- 输出
- 每组数据输出到邮局最小的距离和，回车结束；
- 样例输入
- 2
- 3
- 1 1
- 2 1
- 1 2
- 5
- 2 9
- 5 20
- 11 9
- 1 1
- 1 20
- 样例输出
- 2
- 44
- 要是一点到n点的距离和最小，则此点的x坐标为n点x坐标的中位数，y坐标为n点y坐标的中位数
1 #include <stdio.h> 2 #include <math.h> 3 4 int main(){ 5 int n; 6 int m; 7 int x[21]; 8 int y[21]; 9 int i;10 int j;11 int temp;12 double x_zhong;13 double y_zhong;14 double distance;15 double sum;16 17 scanf("%d",&n);18 19 while(n--){20 scanf("%d",&m);21 22 for(i=0;i<m;i++){23 scanf("%d%d",&x[i],&y[i]);24 }25 26 for(i=0;i<m-1;i++){27 for(j=i+1;j<m;j++){28 if(x[i]>x[j]){29 temp=x[i];30 x[i]=x[j];31 x[j]=temp;32 }33 }34 }35 36 /*if(m%2==1)37 x_zhong=x[m/2];38 39 else40 x_zhong=(x[m/2]+x[m/2-1])/2.0;*/41 42 x_zhong=x[m/2]; //这里中位数求法很有问题，如果m为偶数，中位数应该是中间两个数的平均值 43 44 for(i=0;i<m-1;i++){45 for(j=i+1;j<m;j++){46 if(y[i]>y[j]){47 temp=y[i];48 y[i]=y[j];49 y[j]=temp;50 }51 }52 }53 54 /*if(m%2==1)55 y_zhong=y[m/2];56 57 else58 y_zhong=(y[m/2]+y[m/2-1])/2.0;*/59 60 y_zhong=y[m/2];61 62 sum=0; 63 for(i=0;i<m;i++){64 //distance=(x_zhong-x[i])*(x_zhong-x[i])+(y_zhong-y[i])*(y_zhong-y[i]);65 //distance=sqrt(distance);66 distance=fabs(x[i]-x_zhong)+fabs(y[i]-y_zhong); //要求距离，怎么就这样算了，郁闷 67 sum+=distance;68 }69 printf("%.0lf\n",sum);70 }71 72 return 0;73 }
街区最短路径问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。