fork(5) download
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.Scanner;
  4.  
  5. /* Name of the class has to be "Main" only if the class is public. */
  6. class Ideone
  7. {
  8.  
  9. static Scanner scan;
  10.  
  11. public static void main (String[] args) throws java.lang.Exception
  12. {
  13.  
  14. // declare
  15.  
  16. int [][] matrix = new int [8][8];
  17. int [] distance = new int [8]; int [] pred = new int [8]; int [] visited = new int [8];
  18. int min = 9999 ; int nextnode = 0 ;
  19.  
  20. scan = new Scanner(System.in);
  21.  
  22.  
  23.  
  24.  
  25.  
  26. // input
  27.  
  28. for ( int i = 0 ; i< 8 ; i++)
  29. {
  30. pred [i] = 0 ;
  31. visited[i] = 0 ;
  32.  
  33. for ( int j = 0 ; j< 8 ; j++)
  34.  
  35. {
  36. matrix[i][j] = scan.nextInt();
  37. if (matrix[i][j] ==0 )matrix[i][j] = 9999;
  38. }
  39. }
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46. //dj's algo
  47.  
  48. visited[0] = 1;
  49. distance = matrix[0];
  50. distance[0]=0;
  51.  
  52.  
  53. for ( int c= 0 ; c<8;c++)//all ndes
  54. {
  55. min = 9999;
  56.  
  57.  
  58. for ( int i = 0 ; i< 8 ; i++) // updat distances
  59. {
  60. if ( min > distance [i] && visited[i] !=1 )// if reachable and never visited
  61. {
  62. nextnode=i;
  63. min = distance[i];
  64. }
  65. }
  66.  
  67.  
  68. visited[nextnode] =1;
  69.  
  70. for ( int i =0 ; i < 8 ; i++)
  71. {
  72. if ( visited[i]!=1){
  73.  
  74. if ( min + matrix[nextnode][i] < distance[i])
  75. {
  76. distance[i] = min + matrix[nextnode][i];
  77. pred[i] = nextnode;
  78. }
  79. }
  80. }
  81.  
  82.  
  83.  
  84. }
  85.  
  86.  
  87.  
  88.  
  89. // output
  90.  
  91. for ( int i = 0 ; i< 8 ; i++)
  92. {
  93.  
  94. System.out.print("|" + distance[i]);
  95.  
  96. }System.out.print("|");
  97.  
  98.  
  99.  
  100.  
  101.  
  102. int j;
  103. for ( int i = 0; i < 8 ; i++)
  104. {
  105. if ( i!=0){
  106.  
  107.  
  108. String s = numtocharez(i);
  109. System.out.print("Path = "+ s);
  110.  
  111. j=i;
  112. do {
  113. j = pred[j]; s= numtocharez(j);
  114. System.out.print(" <- " + s);
  115. }while ( j!=0);
  116.  
  117. }
  118. System.out.println();
  119.  
  120. }
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131. }
  132.  
  133.  
  134. public static String numtocharez(int i){return i < 25 && i > -1 ? String.valueOf((char)(i+65)) : null ;}
  135. }
Success #stdin #stdout 0.14s 321344KB
stdin
   0  25 0  85 0  0  105 0 
   0  0  0  0  0  15 0  0 
   0  00 0  55 0  60 0  20 
   0  00 55 0  0 0  35  0
  0  30 00 00  0 0  50 0 
 0   0 15 40 0  0   0  0
 25  0  0 0  0   0   0  0
 0   0  0  0  0  0  0  0
stdout
|0|25|55|80|9999|40|105|75|
Path = B <- A
Path = C <- F <- B <- A
Path = D <- F <- B <- A
Path = E <- A
Path = F <- B <- A
Path = G <- A
Path = H <- C <- F <- B <- A