# -*- coding: utf-8 -*-
# Time : 2023/11/3 17:42
# Author : lirunsheng
# User : l'r's
# Software: PyCharm
# File : Prin.py

import numpy as np


def prim_exists_path(distances):
    num_cities = distances.shape[0]
    visited = set()
    pq = []
    start_node = 0

    visited.add(start_node)
    for neighbor in range(num_cities):
        if neighbor != start_node and np.isfinite(distances[start_node, neighbor]):
            pq.append((distances[start_node, neighbor], start_node, neighbor))

    pq.sort(key=lambda x: x[0])

    while pq:
        weight, node1, node2 = pq.pop(0)
        if node2 not in visited:
            visited.add(node2)
            for neighbor in range(num_cities):
                if neighbor != node2 and np.isfinite(distances[node2, neighbor]):
                    pq.append((distances[node2, neighbor], node2, neighbor))

            pq.sort(key=lambda x: x[0])

    return len(visited) == num_cities


distances = np.array([
    [np.inf, 50, 99, np.inf, 64, np.inf],
    [50, np.inf, 12, 45, 74, 13],
    [99, 12, np.inf, 25, np.inf, 61],
    [np.inf, 45, 25, np.inf, 45, 47],
    [64, 74, np.inf, 45, np.inf, np.inf],
    [np.inf, 13, 61, 47, np.inf, np.inf]
])

print(prim_exists_path(distances))