Этот вопрос от LeetCode 1710 . Это пример Жадного алгоритма . Я думаю, что этот вопрос — хорошее место, чтобы начать решать вопросы жадного алгоритма. Мое решение реализовано на Java.

Надеюсь, вы знакомы с MST Прима. Вы можете увидеть постановку задачи здесь . Я решал эту проблему два раза год назад, не зная стандартного способа решения. Сегодня я снова попытался решить эту проблему, но мне потребовалось много времени, поэтому я решил узнать стандартный способ сделать это, чтобы я мог его запомнить. В MST Prim вы должны выбрать ребра из всех доступных ребер между всеми узлами так, чтобы все узлы были соединены и был только один возможный путь между любыми двумя..