paizaラーニング レベルアップ問題集 巡回セールスマン問題メニュー JavaScript 巡回路長の計算

巡回路長の計算 (paizaランク C 相当)

解答例

巡回路の長さを求めるには、ユークリッド距離を用いて、各都市間の距離を求め、その距離の和を求めればよいです。最後の都市からスタートの都市に戻ってくる距離も足すことに注意します。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//ユークリッド距離の計算式を、関数定義
const dist = (a, b) => {
  return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));    
}; 

//都市の個数 n
const n = Number(lines[0]);
//都市 i の座標 (x_i, y_i) 
const cities = lines.slice(1, n + 1).map(line => line.split(" ").map(Number));

//都市番号の順列で表された巡回路
const p = lines[n + 1].split(" ").map(v => Number(v) - 1);//インデックスで扱うので-1

let l = 0;//巡回路長
for (let i = 0; i <= n - 1; i++) {
  //最後以外
  if (i < n - 1) {
    l += dist(cities[p[i]], cities[p[i + 1]]);
  //最後  
  } else if (i === n - 1) {
    l += dist(cities[p[i]], cities[p[0]]);//最初に戻る  
  }
}
console.log(l);

解答例(Python3の場合参考)

最初に戻る時の場合分けを、%を使ってひとまとめにできます。すなわち、(i + 1) % nとすれば、最後のi=n-1のとき、(i + 1) % n　= 0となり、p[0]で最初の都市に戻ります。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//ユークリッド距離の計算式を、関数定義
const dist = (a, b) => {
  return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));    
}; 

//都市の個数 n
const n = Number(lines[0]);
//都市 i の座標 (x_i, y_i) 
const cities = lines.slice(1, n + 1).map(line => line.split(" ").map(Number));

//都市番号の順列で表された巡回路
const p = lines[n + 1].split(" ").map(v => Number(v) - 1);//インデックスで扱うので-1

let l = 0;//巡回路長
for (let i = 0; i <= n - 1; i++) {
  l += dist(cities[p[i]], cities[p[(i + 1) % n]]);//最初に戻るので%  
}
console.log(l);

解答例(C++の場合参考)

都市 i の座標 (x_i, y_i) の配列citiesや、
都市番号の順列で表された巡回路pは、
forループを使って以下のようにも書けます。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

//ユークリッド距離の計算式を、関数定義
const dist = (a, b) => {
  return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));    
}; 

//都市の個数 n
const n = Number(lines[0]);
//都市 i の座標 (x_i, y_i) 
const cities = Array(n);
for (let i = 0; i < n; i++) {
  cities[i] = lines[i + 1].split(" ").map(Number);
}

//都市番号の順列で表された巡回路
const p = Array(n);
for (let i = 0; i < n; i++) {
  p[i] = lines[n + 1].split(" ").map(Number)[i];
  p[i]--;
} 

let l = 0;//巡回路長
for (let i = 0; i <= n - 1; i++) {
  l += dist(cities[p[i]], cities[p[(i + 1) % n]]);//最初に戻るので%  
}
console.log(l);