fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	static int g[][] = {
  11. 			{0, 1, 0, 1, 0}, 
  12.             {1, 0, 1, 1, 1}, 
  13.             {0, 1, 0, 0, 1}, 
  14.             {1, 1, 0, 0, 1}, 
  15.             {0, 1, 1, 1, 0}
  16.         }; 
  17.     static int dis[][] = {
  18. 			{0, 2, 0, 1, 0}, 
  19.             {2, 0, 3, 3, 2}, 
  20.             {0, 3, 0, 0, 4}, 
  21.             {1, 3, 0, 0, 2}, 
  22.             {0, 3, 4, 2, 0}
  23.         }; 
  24. 	static int[] p = new int[5];
  25. 	static int min = Integer.MAX_VALUE;
  26. 	static HashSet<Integer> set = new HashSet<Integer>();
  27. 	public static void main (String[] args) throws java.lang.Exception
  28. 	{
  29. 		for(int i=0;i<p.length;i++){
  30. 			p[i] = -1;
  31. 		}
  32. 		p[0] = 0;
  33. 		HamiltonCycle(1, 0);
  34. 		System.out.println(min);
  35. 	}
  36. 	public static void HamiltonCycle(int pos, int sum){
  37. 		if(pos == p.length){
  38. 			if(g[p[pos-1]][0] == 1){
  39. 				System.out.println("Cycle!!!");
  40. 				System.out.println(Arrays.toString(p));
  41. 				min = Math.min(min, sum);
  42. 			}
  43. 			return;
  44. 		}
  45. 		for(int i=0;i<p.length;i++){
  46. 			if(isSafe(i, pos)){
  47. 				p[pos] = i;
  48. 				set.add(i);
  49. 				sum = sum+dis[i][p[pos-1]];
  50. 				HamiltonCycle(pos+1, sum);
  51. 				p[pos] = -1;
  52. 				set.remove(i);
  53. 				sum = sum-dis[i][p[pos-1]];
  54. 			}
  55. 		}
  56. 		return;
  57.  
  58. 	}
  59. 	public static boolean isSafe(int v, int pos){
  60. 		if(g[p[pos-1]][v] == 0){
  61. 			return false;
  62. 		}
  63. 		if(set.contains(v)){
  64. 			return false;
  65. 		}
  66. 		return true;
  67. 	}
  68. }
Success #stdin #stdout 0.06s 32192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Cycle!!!
[0, 1, 2, 4, 3]
Cycle!!!
[0, 3, 4, 2, 1]
10
https://ideone.com/iRpUr8
language:
Java (HotSpot 12)
created:
4 years 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!