fork download
copy 
  1. <!-- Run on Opera 10.10 on windows -->
  2. <!-- Copy input to textarea, then push go and wait a while, finally result are displayed in text field -->
  3. <html>
  4. <head>
  5. <script type="text/javascript"
  6.     src="http://maps.google.com/maps/api/js?sensor=false">
  7. </script>
  8. <script type="text/javascript">
  9. Array.prototype.clone = function(){
  10.     return Array.apply(null,this)
  11. }
  12.  
  13. function solve_(idx, matrix, used, cmin, result, clen, cresult)
  14. {
  15.   if(idx == cresult.length-1) {
  16.     clen += matrix[cresult[idx-1]][cresult[idx]];
  17.     if(clen < cmin) {
  18.       return [ clen, cresult ];
  19.     }
  20.     return [ cmin, result ];
  21.   } else {
  22.     for(var i=0;i<used.length;++i) {
  23.       if(used[i] == 0 && cresult[idx-1] != i) {
  24.         clen2 = clen + matrix[cresult[idx-1]][i];
  25.         if(clen2 < cmin) {
  26.           used[i] = 1;
  27.           cresult[idx] = i;
  28.           var res = solve_(idx+1, matrix, used, cmin, result, clen2, cresult);
  29.           cmin = res[0];
  30.           result = res[1].clone();
  31.           used[i] = 0;
  32.         }
  33.       }
  34.     }
  35.     return [ cmin, result ];
  36.   }
  37. }
  38.  
  39. function solve(data, matrix)
  40. {
  41. // solve
  42.   var used = new Array(data.length);
  43.   for(var i=0;i<used.length;++i) used[i] = 0;
  44.   var cresult = new Array(data.length+1);
  45.   cresult[0] = 0;
  46.   cresult[cresult.length-1] = 0;
  47.   used[0] = 1;
  48.   var result = solve_(1, matrix, used, 1000000000000, [], 0, cresult);
  49.  
  50.   var answer = '';
  51.   for(var i=0;i<result[1].length;++i) {
  52.     if(i!=0) answer+=' ';
  53.     answer += data[result[1][i]].name
  54.   }
  55.   document.getElementById('result').value = answer;
  56.   document.getElementById('length').value = result[0];
  57.   alert('finished');
  58. }
  59.  
  60. function calc()
  61. {
  62. // parse input
  63.   var inputs = document.getElementById('input').value.split(/\s+/);
  64.   var data = new Array(inputs.length/3);
  65.   for(var i=0;i<inputs.length/3;++i) {
  66.     data[i] = { name: inputs[i*3], lat: inputs[i*3+1], lng: inputs[i*3+2] };
  67.   }
  68.  
  69.   var matrix = {};
  70.   for(var i=0;i<data.length;++i) {
  71.     matrix[i] = {};
  72.     for(var j=0;j<data.length;++j) if(i!=j) matrix[i][j]=0;
  73.   }
  74.  
  75. // resolve distance
  76.   var directionsService = new google.maps.DirectionsService();
  77.   var requests = data.length * (data.length-1);
  78.   for(var i=0;i<data.length;++i) {
  79.     for(var j=0;j<data.length;++j) {
  80.       if(i!=j) {
  81. 	directionsService.route(
  82.           {
  83. 	    origin: new google.maps.LatLng(data[i]['lat'], data[i]['lng']),
  84. 	    destination: new google.maps.LatLng(data[j]['lat'], data[j]['lng']),
  85. 	    travelMode: google.maps.DirectionsTravelMode.DRIVING
  86. 	  }
  87.           , (function(ii,jj) {
  88.             return function(res, status) {
  89.               if(status == google.maps.DirectionsStatus.OK) {
  90.                 matrix[ii][jj] = res.routes[0].legs[0].distance.value;
  91.                 --requests;
  92.                 if(requests==0) solve(data, matrix);
  93.               }
  94.             }
  95.           })(i,j) // Just using i and j causes error because binded variable becomes 3
  96.         );
  97.       }
  98.     }
  99.   }
  100. }
  101. </script>
  102. </head>
  103. <body>
  104. <textarea id="input" cols="50" rows="10"></textarea>
  105. <input type="button" value="go" onClick="calc()"><br>
  106. <input type="text" id="result" size="100"><br>
  107. <input type="text" id="length" size="30">
  108. </body>
  109. </html>
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5MLY1
language:
JavaScript (SMonkey 60.2.3)
created:
13 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!