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 Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Người tiêu dùng chưa “mặn mà” với TV-3D

Người tiêu dùng chưa “mặn mà” với TV-3D

Mặc dù ngành giải trí 3D trong được khuyến khích trong vài năm qua, người tiêu dùng có vẻ như ít quan tâm đến việc mua một bộ 3D - TV, theo một cuộc khảo sát mới từ Retrevo.

Chữ ký tại email hữu ích thế nào trong marketing?

Chữ ký tại email hữu ích thế nào trong marketing?

Thường thì mọi người hay để chữ ký của mình trong email như một hành động thói quen, làm cho có. Nếu sử dụng đúng cách, chữ ký ở email sẽ trở thành một công cụ tiếp thị mạnh mẽ, không tốn chi phí cho chiến dịch email marketing của bạn.

Tên miền quốc tế

Xử phạt doanh nghiệp sử dụng tên miền quốc tế mà không thông báo

Những doanh nghiệp (DN) sử dụng tên miền quốc tế mà không thông báo hoặc thông báo thiếu thông tin, thông tin không chính xác hoặc thay đổi thông tin mà không thông báo với Bộ Thông tin và Truyền thông sẽ bị phạt từ 3-5 triệu đồng.

BLOG POSTS

 

Wordpress Freelancer

 

Wordpress Freelancer