街區最短路徑問題

時間限制：3000?ms ?|? 內存限制：65535?KB 難度：4 描述

一個街區有很多住戶，街區的街道只能為東西、南北兩種方向。

住戶只可以沿著街道行走。

各個街道之間的間隔相等。

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

動態規劃！

AC碼：

#include <stdio.h> #include <stdlib.h>int comp(const void *p,const void *q) {return (*(int *)p-*(int *)q); }int main() {int n,m,i,x[20],y[20];int min_path;scanf("%d",&n);while(n--){min_path=0;scanf("%d",&m);for(i=0;i!=m;i++)scanf("%d %d",&x[i],&y[i]);qsort(x,m,sizeof(int),comp);//將x數組升序排序qsort(y,m,sizeof(int),comp);for(i=0;i<m/2;i++) //find the min Coordinatemin_path += x[m-i-1]-x[i]+y[m-i-1]-y[i];printf("%d\n",min_path);}return 1; }

總結

以上是生活随笔為你收集整理的NYOJ 7 街区最短路径问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。