The question:
　　12個工廠分布在一條東西向高速公路的兩側(cè)，工廠距離公路最西端的距離分別是0、4、5、10、12、18、27、30、31、38、39、47.
　　在這12個工廠中選取3個原料供應(yīng)廠，使得剩余工廠到最近的原料供應(yīng)廠距離之和最短，問應(yīng)該選哪三個廠 ？


The code:
1 import java.util.Scanner; 2 3 public class Main { 4 5 6 public static void main(String[] argv){ 7 Scanner in = new Scanner(System.in); 8 // 存放結(jié)果.... 9 int min_start=0; 10 int min_end=0; 11 int min_RESULT=0; 12 13 //輸入..... 14 int M =in.nextInt(); 15 int[] s = new int[M]; 16 for(int i=0; i<M; i++){ 17 s[i]=in.nextInt(); 18 } 19 in.close(); 20 21 //處理.... 22 int[][] F_length = new int [M][2]; //如果選單個 第i個點建廠 F_length[i][0]即左邊到廠的距離和 F_length[i][1]即右邊到廠的距離和 23 for(int j=0; j<M; j++){ 24 int sum_0=0; 25 int sum_1=0; 26 if(j==0){ 27 for(int k=0; k<M; k++){ 28 if(j>=k) 29 sum_0=sum_0+s[j]-s[k]; 30 else 31 sum_1=sum_1+s[k]-s[j]; 32 } 33 } 34 else{ 35 sum_0=F_length[j-1][0]+j*(s[j]-s[j-1]); 36 sum_1=F_length[j-1][1]-(M-j)*(s[j]-s[j-1]); 37 } 38 39 F_length[j][0]=sum_0; 40 F_length[j][1]=sum_1; 41 //System.out.println(" "+j+": "+sum_0+" "+sum_1); 42 } 43 //獲取建兩個廠的結(jié)果 44 int[][] result = new int[M][M]; //如果選兩個 第i，k個點建廠 result[i][k]即所有點到最近廠的距離和 45 for(int i=0; i<M;i++){ 46 47 for(int j=i+1; j<M; j++){ 48 result[i][j]=F_length[i][0]+F_length[j][1]; 49 for(int t=i+1;t<j;t++){ 50 int x= s[t]-s[i]; 51 int y= s[j]-s[t]; 52 if(x>y) 53 x=y; 54 result[i][j]=result[i][j]+x; 55 } 56 if(min_RESULT==0||min_RESULT>result[i][j]){ 57 min_start=i; 58 min_end=j; 59 min_RESULT=result[i][j]; 60 } 61 /* 62 else{ 63 if(min_RESULT>result[i][j]){ 64 min_start=i; 65 min_end=j; 66 min_RESULT=result[i][j]; 67 } 68 69 }*/ 70 71 System.out.println(" "+i+" "+j+" "+result[i][j]); 72 } 73 74 } 75 76 System.out.println("The first is "+min_start+"."); 77 System.out.println("The second is "+min_end+"."); 78 System.out.println("The length is "+min_RESULT+"."); 79 80 } 81 }

測試用例：

/*
12
0
4
5
10
12
18
27
30
31
38
39
47
*/

Result:?

The first is 2.
The second is 8.
The length is 67.

? ?

轉(zhuǎn)載于:https://www.cnblogs.com/udld/p/4724932.html

總結(jié)

以上是生活随笔為你收集整理的公路建厂最短路径问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。