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: asaleotestf@gmail.com
  • 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

 
Bí ẩn trong phím Option của Mac OS X

Bí ẩn trong phím Option của Mac OS X

Bản thân Mac OS X có rất nhiều những bí mật mà bạn phải tự tìm kiếm bởi chúng không nằm trong bất cứ hướng dẫn sử dụng nào.

Cải thiện Performance và Scalability trong Drupal Site

Cải thiện Performance và Scalability trong Drupal Site

Here at Achieve Internet, we perform a lot of system reviews for our clients to help them improve the performance and scalability of their sites.  From these numerous system reviews, we've identified 5 common things that are missing from many hosting configurations.

DATC đối mặt nguy cơ mất vốn, thanh khoản kém

DATC đối mặt nguy cơ mất vốn, thanh khoản kém

Công ty TNHH MTV Mua bán nợ Việt Nam (DATC) không thực hiện đầy đủ chức năng nhiệm vụ chính là mua bán nợ và đầu tư dài hạn tái cấu trúc cho doanh nghiệp, sử dụng vốn hiệu quả thấp; tiền gửi và cho vay không đúng chức năng nhiệm vụ, thanh khoản kém và có nguy cơ mất vốn.