空起床店面 面经 有向图最短距离

多谢lz，这题目的input是什么啊？

JS Solution,

Please give me any comments :)

// Implement a priority queue, sorted by cost
class PQueue {
  constructor() {
    this.nodes = [];
  }
  enqueue(key, cost) {
    this.nodes.push({cost: cost, key: key});
    this.sort();
  }
  sort() {
    this.nodes.sort((a,b) => a.cost - b.cost);
  }
  dequeue() {
    let node = this.nodes.shift();
    return node.key;
  }
  isEmpty() {
    return this.nodes.length === 0;
  }

}

// Define a Wizard class with id and friends
class Wizard {
  constructor(id) {
    this.id = id;
    this.friends = new Set();
  }
}

// Define a friend relationship and the 'cost' lol
class Relationship {
  constructor(id,cost) {
    this.id = id;
    this.cost = cost;
  }
}

function introducingWizard(wizards, start, end) {
  let visited = new Set();
  let cost = {};
  let graph = {};
  let previous = {};
  let path = [];
  let nodes = new PQueue();
  let MAX = Number.MAX_SAFE_INTEGER;

  // Put the first node into our PQ, with cost 0.
  nodes.enqueue(start, 0);
  cost[start] = 0;

  // Build wizard relationship.
  for (let wizard of wizards) {
    if (wizard[1] !== start ) cost[wizard[1]] = MAX;
    let relationship = new Relationship(wizard[1], wizard[2]);
    if (graph[wizard[0]] === undefined) graph[wizard[0]] = new Wizard(wizard[0]);
    graph[wizard[0]].friends.add(relationship);
  }
  // Dijkstra
  while (!nodes.isEmpty()) {
    let curr = nodes.dequeue();

    if (!visited.has(curr)) {
      visited.add(curr);
      // If we get to the end wizard, we construct the path via previous visited table 'previous'
      if (curr === end) {
        while (previous[curr] !== undefined) {
          path.push(curr);
          curr = previous[curr];
        }
        break;
      }
      // Otherwise we keep searching for the next friend with minCost
      for (let friend of graph[curr].friends) {
        if (!visited.has(friend.id)) {
          let minCost = cost[curr] + friend.cost;
          if (minCost < cost[friend.id]) {
            cost[friend.id] = minCost;
            previous[friend.id] = curr;
            nodes.enqueue(friend.id, minCost);
          }
        }
      }
    }
  }
  // Push the start to the path and reverse it; return the path as well as the minCost for end.
  path.push(start);
  path.reverse();
  return [path, cost[end]];
}

let wizards = [
  [0,1,0],
  [2,3,0],
  [1,4,9],
  [3,2,1],
  [5,6,1],
  [2,6,16],
  [5,3,0],
  [7,9,4],
  [8,9,1],
  [4,6,4],
  [1,3,0],
  [6,3,0],
  [6,8,4],
  [4,2,0],
  [5,8,9]
];

console.log(introducingWizard(wizards, 0, 6));