[Vssue]kamacoder/0053.寻宝-prim.md

[youngyangyang04]

https://www.programmercarl.com/kamacoder/0053.%E5%AF%BB%E5%AE%9D-prim.html

[DEZREMNACUI]

import { createInterface } from "readline/promises";

const rl = createInterface({
  input: process.stdin,
});

const readline = async () =>
  (await rl[Symbol.asyncIterator]().next()).value as string;

const main = async () => {
  const [dots, edges] = (await readline()).split(" ").map(Number);
  const grid = Array.from({ length: dots + 1 }, () =>
    Array.from({ length: dots + 1 }, () => 0)
  );
  for (let i = 0; i < edges; i++) {
    const [s, t, v] = (await readline()).split(" ").map(Number);
    grid[s][t] = v;
    grid[t][s] = v;
  }
  const minDist = new Array(dots + 1).fill(Infinity) as number[];
  minDist[1] = 0;
  const isInTree = Array.from({ length: dots + 1 }, () => false);
  for (let i = 1; i < grid.length; i++) {
    let minValue = Infinity;
    let curr: null | number = null;
    for (let j = 1; j < grid[0].length; j++) {
      if (minDist[j] < minValue && !isInTree[j]) {
        minValue = minDist[j];
        curr = j;
      }
    }
    isInTree[curr!] = true;
    // console.log(curr)
    for (let j = 1; j < grid.length; j++) {
      if (!isInTree[j] && grid[curr!][j] !== 0 && grid[curr!][j] < minDist[j]) {
        minDist[j] = grid[curr!][j];
      }
    }
  }

  console.log(minDist.slice(1).reduce((acc, curr) => acc + curr));
};

main();