matbensch

Untitled

Feb 21st, 2022
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.73 KB | None | 0 0
  1. import java.util.Arrays;
  2.  
  3. public class gt_tsp
  4. {
  5.  
  6.     static int oo = (int)1e9;
  7.     static int[][] dp;
  8.    
  9.     static boolean has(int m,int i)
  10.     {
  11.         if((m>>i & 1) == 1) return true;
  12.         return false;
  13.     }
  14.    
  15.     static int vis(int m,int i)
  16.     {
  17.         return (m | (1<<i));
  18.     }
  19.    
  20.     static int tsp(int[][] adj,int m,int i)
  21.     {
  22.         if(dp[m][i]!=-1)
  23.             return dp[m][i];
  24.         if(m==(1<<adj.length)-1)
  25.             return adj[i][0];
  26.        
  27.         int min = oo;
  28.         for(int j=0;j<adj.length;j++)
  29.         {
  30.             if(adj[i][j]!=0 && !has(m,j))
  31.                 min = Math.min(min, adj[i][j]+tsp(adj,vis(m,j),j));
  32.         }
  33.         return dp[m][i] = min;
  34.     }
  35.    
  36.     static int tsp(int[][] adj)
  37.     {
  38.         dp = new int[1<<(adj.length)][adj.length];
  39.         for(int[] e:dp) Arrays.fill(e, -1);
  40.         return tsp(adj,1,0);
  41.     }
  42.    
  43. }
  44.  
Advertisement
Add Comment
Please, Sign In to add comment