fork download 
  1. #include <stdio.h>
  2.  
  3. int n, c[105][105], X[105], visited[105];
  4. int dis = 0;
  5. int min = 1e9;
  6.  
  7. // Hàm tính chi phí nhỏ nhất cmin giữa các thành phố chưa đi qua
  8. int findMin(int i){
  9.     int cmin = 1e9;
  10.     for(int j = 1; j<= n; j++){
  11.         if(c[i][j] < cmin){
  12.             cmin = c[i][j];
  13.         }
  14.     }
  15.     return cmin;
  16. }
  17. void Try(int i){
  18.     for(int j = 2; j<= n; j++){
  19.         if(visited[j] == 0){
  20.             X[i] = j;  
  21.             visited[j] = 1;         
  22.             dis += c[X[i-1]][X[i]];
  23.             // Tính chi phó nhỏ nhất cmin giữa các thành phố chưa đi qua
  24.             int cmin = findMin(X[i]);   // cmin là chi phí nhỏ nhất từ thành phố hiện tại
  25.             // Nhánh cận: Kiểm tra nếu dis cộng với chi phí ước tính còn lại là lớn hơn min đang có ==> cắt nhánh
  26.             if(dis + (n-i+1)*cmin >= min){
  27.                 dis -= c[X[i-1]][X[i]];
  28.                 visited[j] = 0;
  29.                 return; // cắt  nhánh
  30.             }
  31.  
  32.             if(i == n){
  33.                 if(dis + c[X[i]][1] < min){
  34.                     min = dis + c[X[i]][1];
  35.                 }
  36.             }
  37.             else{
  38.                 Try(i+1);
  39.             }
  40.             visited[j] = 0;
  41.             dis -= c[X[i-1]][X[i]];
  42.         }
  43.     }
  44. }
  45.  
  46. int main(){
  47.     scanf("%d", &n);
  48.     for(int i = 1; i<= n; i++){
  49.         for(int j = 1; j<= n; j++){
  50.             scanf("%d", &c[i][j]);
  51.         }
  52.     }
  53.     X[1] = 1;
  54.     visited[1] = 1;
  55.     Try(2);
  56.     printf("%d", min);
  57. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
1000000000
https://ideone.com/3YkQvY
language:
C (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!