Viết chương trình tính đường đi ngắn nhất - đường đi Hamiton cho nhân viên

Viết chương trình tính đường đi ngắn nhất - đường đi Hamiton cho nhân viên

Nhân viên giao bánh piza phải giao bánh cho N khách hàng. Từ cửa hàng bánh , anh ta phải đi giao bánh cho N khách hàng sau đó trở về nhà của mình. Vị trí của của hàng bánh, nhà của anh ta và của khách hàng theo mẫu sau (x,y). Khoảng cách giữa 2 vị trí (x1,y1) và (x2,y2) được tính theo công thức sau: |x1-x2| + |y1-y2|.

Hãy viết chương trình tính đường đi ngắn nhất cho nhân viên trên.

[Input]

Có 10 test case được chứa trong file dữ liệu đầu vào OPTIMALPATH.INP. Dòng đầu ghi số khách hàng N. Dòng sau ghi vị trí (x,y) của văn phòng, nhà của nhân viên và của N khách hàng.

[Output]

Ghi ra file OPTIMALPATH.OUT đường đi ngắn nhất cho mỗi test case. Với mỗi test case được bắt đầu bằng #C.

[I/O example]

5
0 0 100 100 70 40 30 10 10 5 90 70 50 20
6
88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14
7
22 47 72 42 61 93 8 31 72 54 0 64 26 71 93 87 84 83
8
30 20 43 14 58 5 91 51 55 87 40 91 14 55 28 80 75 24 74 63
9
3 9 100 100 16 52 18 19 35 67 42 29 47 68 59 38 68 81 80 37 94 92
10
39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36
10
26 100 72 2 71 100 29 48 74 51 27 0 58 0 35 2 43 47 50 49 44 100 66 96
10
46 25 16 6 48 82 80 21 49 34 60 25 93 90 26 96 12 100 44 69 28 15 57 63
10
94 83 72 42 43 36 59 44 52 57 34 49 65 79 14 20 41 9 0 39 100 94 53 3
10
32 79 0 0 69 58 100 31 67 67 58 66 83 22 44 24 68 3 76 85 63 87 7 86

[Output]

#1 200
#2 304
#3 265
#4 307
#5 306
#6 366
#7 256
#8 399
#9 343
#10 391

Chương trình cài đặt.

#include<iostream>

#define myABS(value) ((value < 0) ? -(value) : (value))

using namespace std;

int matrix[12][12];

int position[12][2];

int minPath;

bool isVisited[12];

int customerNo;

void DFS(int vertice, int pathLength, int verticeCount){

 if(verticeCount == customerNo+1){

  if(pathLength + matrix[vertice][1] < minPath){

   minPath = pathLength + matrix[vertice][1];

  }

  return;

 }

 for(int i=2;i<customerNo+2;i++){

  if(!isVisited[i] && i != vertice && pathLength + matrix[vertice][i] < minPath){

   isVisited[i] = true;

   DFS(i, pathLength + matrix[vertice][i], verticeCount+1);

   isVisited[i] = false;

  }

 }

}

int main(){

 freopen("OPTIMALPATH.INP","r",stdin);

 freopen("OPTIMALPATH.OUT","w", stdout);

 customerNo;

 int tc;

 for(tc=1;tc<=10;tc++){

  cin>>customerNo;

  for(int i=0;i<customerNo + 2;i++){

   cin>>position[i][0]>>position[i][1];

  }

  for(int i=0;i<customerNo+1;i++){

   for(int j=i;j<customerNo+2;j++){

    if(i==j){

     matrix[i][j]=0;

    }else{

     matrix[i][j] = matrix[j][i] =  myABS(position[i][0] - position[j][0]) + myABS(position[i][1] - position[j][1]);

    }

   }

  }

  minPath = 1000000000;

  for(int i=0;i<customerNo+2;i++) isVisited[i] = false;

  isVisited[0] = true;

  DFS(0,0,1);// office's index.

  cout<<"#"<<tc<<" "<<minPath<<endl;

  

 }


 return 0;

}
Bạn thấy bài viết này như thế nào?: 
Average: 10 (7 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Giới thiệu những kiến thức cơ bản về Apache Hive

Giới thiệu những kiến thức cơ bản về Apache Hive

Như đã biết thuật ngữ “big data” được sử dụng để nói đến tập dữ liệu lớn trong đó hàng ngày nó gia tăng về cả khối lượng

Bảng xếp hạng 20 điện thoại tốt nhất thế giới trong tháng 12/2012

Galaxy S III, One X+, iPhone 5 hay Nexus 4 và Note II vẫn là năm cái tên dẫn đầu trong bảng xếp hạng tháng này.

Hướng dẫn tăng like facebook số lượng lớn bằng Addmefast

Bạn vào mục ADD SITE/PAGE thên link mà bạn muốn tăng like hay gì cho nó.

Tomdesgin.vn

 

Drupal Services