Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- public class gt_tsp
- {
- static int oo = (int)1e9;
- static int[][] dp;
- static boolean has(int m,int i)
- {
- if((m>>i & 1) == 1) return true;
- return false;
- }
- static int vis(int m,int i)
- {
- return (m | (1<<i));
- }
- static int tsp(int[][] adj,int m,int i)
- {
- if(dp[m][i]!=-1)
- return dp[m][i];
- if(m==(1<<adj.length)-1)
- return adj[i][0];
- int min = oo;
- for(int j=0;j<adj.length;j++)
- {
- if(adj[i][j]!=0 && !has(m,j))
- min = Math.min(min, adj[i][j]+tsp(adj,vis(m,j),j));
- }
- return dp[m][i] = min;
- }
- static int tsp(int[][] adj)
- {
- dp = new int[1<<(adj.length)][adj.length];
- for(int[] e:dp) Arrays.fill(e, -1);
- return tsp(adj,1,0);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment