Question

C语言，最短路问题，求解！

设平面上一共有N个整数点(xi,yi)(0< =i< N),现在从中任选出M(M< =N)个点，再从中任意选择一个点(x,y)，你能计算出点(x,y)和这M个点距离之和的最小值吗?
其中，点(x,y)和点(xi,yi)之间的距离定义为：|x-xi|+|y-yi|。

Input：首先输入一个数cas，代表下面共有cas组测试数据。
对于每组数据首先输入数N，M，(1< =N< =100)。代表共有N个点，并选择其中的M个。然后接下来N行，依次输入这N个点的坐标(xi,yi)(0< =i< N)。

Output：输出距离和的最小值，输出一组后换行输出另一组。(所有结果都在int范围内)

Sample Input

2
3 2
1 0
10 0
12 0

3 2
1 1
2 2
4 4

Sample Output

2
2

求程序！！！！
有加分！！！速度.....

Answer 1

给你matlab的程序行不？呵呵 这个只要看懂算法就可以自己来的
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;

d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];

for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}

for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t))
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))

}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";

}
/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100

追问

是我没看懂你的还是你没看懂我的意思？
只需要一个输出结果，嗯嗯，是在M个点里面找到和其他点距离最小的然后输出，M是随机的在N里面选择，只要最后算出来的是距离最小就好了。

Answer 2

[code=C/C++][/code]#include"stdio.h"
#include"string.h"
#define Lm 20000
int main()
{
int map[102][102],i,j,k,m,n,a,b;
while(scanf("%d%d",&n,&m)&&(m||n)){
memset(map,0,sizeof(map));
while(m--) {scanf("%d%d",&a,&b);scanf("%d",&map[a][b]);map[b][a]=map[a][b];}
for(i=0;i<102;i++)
for(j=0;j<102;j++) if(map[i][j]==0) map[i][j]=Lm;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
{
if(i==j||i==k||k==j) continue;
if(map[i][k]<Lm&&map[k][j]<Lm&&map[i][j]-map[i][k]>map[k][j])
{map[i][j]=map[i][k]+map[k][j];}
}
printf("%d\n",map[1][n]);
}
}