[プログラマー/JavaScript]タクシー料金

問題の説明📝

夜遅く帰宅した時、安全のためタクシーをよく利用していた武智は最近残業が多くなってきたので、タクシー代の節約を考えていた.「無知」は、自分がタクシーを使うとき、同僚の魚皮奇も自分の方向に似たタクシーをよく使うことを発見した.「無知」は「魚の日」と耳の方向が似ていて、現地でタクシーを乗り合わせればタクシー代をどれだけ節約できるか、「魚の日」に乗り合わせようと提案しています.

上記の例の図は、移動可能半径の6地点間のタクシーの移動可能なタクシー路線と予想料金を示している.
図中のAとBの2人は出発点4番から出発して、タクシーで家に帰るつもりです.Aの家は6日に、Bの家は2日に、二人とも帰宅予定の最低タクシー代はいくらですか.
図中の円は点を表し、円内の数字は点番号を表す.
n個の分岐点がある場合は、1〜nの分岐点番号を使用します.
タクシーの支点間の走行経路を幹線道路と呼び、幹線道路に表示される数字は2つの支点間の予想タクシー料金を表す.
幹線は便利な垂直線として表示されます.
上図の例では、4番から1番まで(4→1)または1番から4番まで(1→4)の場合、移動方向によってタクシー料金が変化しない見込みです.
予想される最低タクシー料金は以下のように計算されます.
4→1→5:A、Bはタクシーに乗ります.タクシー料金は10+24=34元と予想されています.
5→6:A自分でタクシーに乗ります.タクシー代は2元の予定です.
5→3→2:B自分でタクシーに乗ります.タクシー料金は24+22=46元と予想されています.
A、Bともに帰宅前の最低タクシー代は34+2+46=82元.

に答える

これは典型的なグラフィック問題であり、真ん中に最適なノードを選択する必要があります.
マルチセグメント、FDD、ポーリングを選択する必要があります.
JSにはheap構造がないため,複数の解析に失敗する.

マルチアウトレット失敗

function solution(n, s, a, b, fares) {
  let answer = Infinity;
  const adj = Array.from({ length: n + 1 }, () => []);

  fares.forEach((route) => {
    adj[route[0]].push({
      to: route[1],
      cost: route[2],
    });
    adj[route[1]].push({
      to: route[0],
      cost: route[2],
    });
  });

  const dijkstra = (start, end) => {
    const dist = Array(n + 1).fill(Infinity); // 최단 거리 저장
    const queue = [];

    dist[start] = 0; // 출발 지점
    queue.push({ to: start, cost: 0 });

    while (queue.length) {
      const { to } = queue.shift();

      adj[to].forEach((nextNode) => {
        if (dist[nextNode.to] > dist[to] + nextNode.cost) {
          dist[nextNode.to] = dist[to] + nextNode.cost;
          queue.push(nextNode);
        }
      });
    }

    return dist[end];
  };

  for (let i = 1; i <= n; i++) {
    answer = Math.min(answer, dijkstra(s, i) + dijkstra(i, a) + dijkstra(i, b));
  }

  return answer;
}

フロイドとシエルは成功した

function solution(n, s, a, b, fares) {
  let answer = Infinity;
  const adj = Array.from({ length: n + 1 }, () => Array(n + 1).fill(Infinity));

  fares.forEach(([start, end, cost]) => {
    adj[start][end] = cost;
    adj[end][start] = cost;
  });

  for (let mid = 1; mid <= n; mid++) {
    for (let start = 1; start <= n; start++) {
      for (let end = 1; end <= n; end++) {
        if (start === end) {
          adj[start][end] = 0;
        }

        if (adj[start][end] > adj[start][mid] + adj[mid][end]) {
          adj[start][end] = adj[start][mid] + adj[mid][end];
          adj[end][start] = adj[start][mid] + adj[mid][end];
        }
      }
    }
  }

  for (let mid = 1; mid <= n; mid++) {
    answer = Math.min(answer, adj[s][mid] + adj[mid][a] + adj[mid][b]);
  }

  return answer;
}