fork(1) download
copy 
  1. <!doctype html>
  2. <html>
  3. <head>
  4. <meta http-equiv="content-type" content="text/html; charset=UTF-8"/>
  5. <title>Maps TSP</title>
  6. <script src="http://maps.google.com/maps?file=api&amp;v=2&amp;sensor=false" type="text/javascript"></script>
  7. <script type="text/javascript">
  8. function calculate() {
  9. 	if (GBrowserIsCompatible()) {
  10. 		var map = new GMap2(document.getElementById("map"));
  11. 		map.setMapType(G_NORMAL_MAP);
  12. 		map.addControl(new GLargeMapControl());
  13. 		map.addControl(new GMapTypeControl());
  14. 		var directions = new GDirections(map, null);
  15. 		GEvent.addListener(directions, "error", function() {
  16. 			var message = document.getElementById("message");
  17. 			message.appendChild(document.createTextNode(directions.getStatus().code));
  18. 			message.appendChild(document.createElement("br"));
  19. 		});
  20. 		directions.loadFromWaypoints(
  21. 			toGLatLng(document.getElementById("input").value.split("\n")),
  22. 			{ locale: "ja_JP" }
  23. 		);
  24. 		var message = document.getElementById("message");
  25. 		message.innerHTML = "";
  26. 		var input = document.getElementById("input").value.split("\n");
  27. 		var results = new Array();
  28. 		for (var i = 0; i < input.length; i++) {
  29. 			for (var j = 0; j < input.length; j++) {
  30. 				results.push([input[i], input[j]]);
  31. 			}
  32. 		}
  33. 		setInterval(function(){
  34. 			if (results.length == 0 ) {
  35. 				return;
  36. 			}
  37. 			var array = results.shift();
  38. 			var directions = new GDirections(null, null);
  39. 			var route = toPlaceNames(array);
  40. 			GEvent.addListener(directions, "load", function() {
  41. 				var message = document.getElementById("message");
  42. 				message.appendChild(document.createTextNode(route.join(" ") + " " + directions.getDuration().seconds));
  43. 				message.appendChild(document.createElement("br"));
  44. 			});
  45. 			GEvent.addListener(directions, "error", function() {
  46. 				var message = document.getElementById("message");
  47. 				message.appendChild(document.createTextNode(directions.getStatus().code));
  48. 				message.appendChild(document.createElement("br"));
  49. 			});
  50. 			directions.loadFromWaypoints(
  51. 				toGLatLng(array),
  52. 				{ locale: "ja_JP" }
  53. 			);
  54. 		}, 500);
  55. 	}
  56. }
  57.  
  58. if (GBrowserIsCompatible()) {
  59. 	GEvent.addDomListener(window, "unload", function() { GUnload(); });
  60. }
  61.  
  62. function toPlaceNames(array) {
  63. 	var ret = new Array();
  64. 	for (var index in array) {
  65. 		var items = array[index].split(" ");
  66. 		ret.push(items[0]);
  67. 	}
  68. 	return ret;
  69. }
  70.  
  71. function toGLatLng(array) {
  72. 	var ret = new Array();
  73. 	for (var index in array) {
  74. 		var items = array[index].split(" ");
  75. 		ret.push(new GLatLng(items[1], items[2]));
  76. 	}
  77. 	return ret;
  78. }
  79. </script>
  80. </head>
  81. <body>
  82. <h1>Maps TSP</h1>
  83. <h2>入力</h2>
  84. <textarea id="input" style="width: 25em; height: 13em;">東京駅 35.681382 139.766084
  85. 首里城 26.216991 127.719362
  86. 三内丸山遺跡 40.811225 140.695649
  87. 坂本竜馬記念館 33.496428 133.571845
  88. 五稜郭 41.796868 140.756794
  89. 襟裳岬 41.926490 143.246642
  90. 国会正門前 35.676293 139.746927
  91. 京都大学 35.025280 135.780910
  92. 東京国際フォーラム 35.676651 139.763651
  93. 京都リサーチパーク 34.994707 135.740076</textarea>
  94. <input type="button" value="計算する" onClick="calculate()"/>
  95. <h2>出力</h2>
  96. <div id="map" style="width: 400px; height: 300px; border: 1px solid gray; float: left;">ここに地図が表示されます。</div>
  97. <div id="message" style="margin-left: 400px; padding-left: 1em;">ここにメッセージが表示されます。</div>
  98. </body>
  99. </html>
  100. --------------------------------------------------------------------------------
  101. import java.io.UnsupportedEncodingException;
  102. import java.util.ArrayList;
  103. import java.util.HashMap;
  104. import java.util.LinkedHashSet;
  105. import java.util.List;
  106. import java.util.Map;
  107. import java.util.Scanner;
  108. import java.util.Set;
  109. import java.util.Stack;
  110.  
  111. public class TSP {
  112.  
  113. 	static long minDistance = Long.MAX_VALUE;
  114.  
  115. 	public static void main(String[] args) throws UnsupportedEncodingException {
  116. 		Set<String> places = new LinkedHashSet<String>();
  117. 		Map<String, Long> distances = new HashMap<String, Long>();
  118. 		Scanner scanner = new Scanner(System.in);
  119. 		while (scanner.hasNextLine()) {
  120. 			String line = scanner.nextLine();
  121. 			String[] items = line.split(" ");
  122. 			if (items.length == 3) {
  123. 				String from = items[0];
  124. 				String to = items[1];
  125. 				long distance = Long.parseLong(items[2]);
  126. 				places.add(from);
  127. 				distances.put(from + "-" + to, distance);
  128. 			} else {
  129. 				System.out.println("wrong format : " + line);
  130. 			}
  131. 		}
  132. 		scanner.close();
  133. 		enumurate(new ArrayList<String>(places), new Stack<String>(), distances);
  134. 		System.out.println("終了");
  135. 	}
  136.  
  137. 	static void enumurate(List<String> in, Stack<String> out, Map<String, Long> distances) {
  138. 		if (in.isEmpty()) {
  139. 			out.push(out.get(0));
  140. 			long distance = 0;
  141. 			for (int i = 1; i < out.size(); i++) {
  142. 				distance += distances.get(out.get(i - 1) + "-" + out.get(i));
  143. 			}
  144. 			if (distance < minDistance) {
  145. 				minDistance = distance;
  146. 				System.out.println(out.toString().replace(", ", " ") + ", " + distance);
  147. 			}
  148. 			out.pop();
  149. 		} else {
  150. 			for (int i = 0; i < in.size(); i++) {
  151. 				String value = in.get(i);
  152. 				in.remove(i);
  153. 				out.push(value);
  154. 				enumurate(in, out, distances);
  155. 				in.add(i, value);
  156. 				out.pop();
  157. 			}
  158. 		}
  159. 	}
  160. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kZ3W6
language:
Java (HotSpot 12)
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!