0
回答
“街区最短路径问题”中得出结果的混乱!
利用AWS快速构建适用于生产的无服务器应用程序,免费试用12个月>>>   

这是那个acm的一个编程题,题目要求是这样的:

描述一个街区有很多住户,街区的街道只能为东西、南北两种方向。

住户只可以沿着街道行走。

各个街道之间的间隔相等。

用(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


我的实现是这样子的:

import java.util.Scanner;

class theShort{
	public static void main(String[] arguments) {
		int i,j,m,t,n,test,temp,lines,numbers;
		int x[]=new int[20];
		int y[]=new int[20];
		//变量定义结束
		
		//System.out.println("输入测试的组数!");
		Scanner scanner=new Scanner(System.in);
		lines = scanner.nextInt();
		
		for(t=1;t<=lines;t++)
		{
			//System.out.println("请输入用户数目!");
			numbers=scanner.nextInt();
			for(n=1;n<=numbers;n++)
			{
				x[n-1]=scanner.nextInt();
				y[n-1]=scanner.nextInt();
			}
			
		test=0;
		temp=0;
		for(m=0;m<numbers;m++)
			test=test+Math.abs(x[m]-1)+Math.abs(y[m]-1);
		
		for(i=1;i<100;i++)
			for(j=1;j<100;j++)
				{
					for(m=0;m<numbers;m++)
						temp=temp+Math.abs(x[m]-i)+Math.abs(y[m]-j);
					if (temp<test)
						test=temp;
					temp=0;
				}
		System.out.println(test);
		}
		
	}
}
测试时,单个输入结果都正确,但是如果这样
输入的数据是:
2
3
1 1
2 1
1 2
5
2 9
5 20
11 9
1 1
1 20
第一组的结果“3”应该是在“1 2” 的下边出现,却莫名其妙的出现在第二组的数据“1 1”后边,但实际算结果是正确的,请问这是什么原因呀,java学习啦不久,请大家多多指教!
有何意见尽管批评!

<无标签>
举报
gudda
发帖于5年前 0回/286阅
顶部