第一行包含两个整数 n(1<=n<=1x10 6 ),m(1<=m<=1x10 6 ) 表示该图共有 n 个结点和 m 条无向边。 接下来 m 行每行包含三个整数 x i ​ ,y i ​ ,z i ​ ，表示有一条长度为 z i ​ 的无向边连接结点 x i ​ ,y i ​ 。

### 回答1：
题目描述：有一个图共有n个结点和m条无向边。接下来m行每行包含三个整数x, y, z表示无向边 (x, y) 的长度为 z。

这道题是关于图的最小生成树问题，使用Prim算法或Kruskal算法可以得到最小生成树。其中，Prim算法是基于点的贪心；Kruskal算法是基于边的贪心。

Prim算法的思路：以一个点开始，然后依次加入不在当前生成树中的离当前生成树最近的点，并选择与当前生成树相连的最短的边。

Kruskal算法的思路：按照边从小到大排序，然后依次加入不产生环的边，直到边数达到n-1。具体实现需要使用并查集维护每个点所在的连通块。

使用Prim或Kruskal算法可以求出最小生成树的权值之和。

### 回答2：
题目描述：

给定一个无向带权图，求出从某个点出发到各个点的最短路径，其中边权均为正整数。

思路：

使用迪杰斯特拉算法求出从起点到各个点的最短路径。

具体步骤如下：

1. 初始化：将所有点的距离先设为正无穷大，然后将起点的距离设为0。

2. 将起点加入一个集合S中，表示已经求出了起点到S中点的最短路径。

3. 以起点为基准点，扫描与该点相邻的所有点，并计算从起点出发到该点的距离。

4. 如果新的距离小于旧的距离，则更新该点的距离，并将该点加入集合S中。

5. 重复步骤3和步骤4，直到S包含所有点。

代码实现：

import heapq

def dijkstra(graph, start):
    """
    :param graph: 无向带权图的邻接表表示，graph[i]表示与顶点i相连的顶点以及边的权重
    :param start: 起点
    :return: 返回从起点到各个点的最短路径
    """
    n = len(graph) # 图中节点个数
    dist = [float("inf")] * n # 初始化所有节点距离为正无穷大
    dist[start] = 0 # 起点的距离为0

    pq = [(0, start)] # 小根堆，存放待遍历的节点
    while pq:
        d, node = heapq.heappop(pq) # 取出距离最小的节点

        if d > dist[node]: # 如果该节点已经被遍历过，则跳过
            continue

        for neighbor, weight in graph[node]: # 遍历该节点的所有邻居
            new_dist = d + weight # 计算新的距离
            if new_dist < dist[neighbor]: # 如果新距离小于原始距离
                dist[neighbor] = new_dist # 更新最短距离
                # 将该节点加入小根堆中
                heapq.heappush(pq, (new_dist, neighbor))

    return dist

时间复杂度：

迪杰斯特拉算法的时间复杂度为O(E log V)，E为边的数量，V为节点的数量。

### 回答3：
这道题目是求图中任意两点之间的最短距离。对于这个问题，可以采用Dijkstra算法或者Floyd算法进行求解。

Dijkstra算法是一种贪心算法，用于解决单源最短路径问题，在每一次迭代中选择距离起点最近的点作为中间点，更新起点到其他点的距离，逐步扩展到所有点。具体实现过程为：首先创建一个集合S，存储已知最短距离的点；创建一个集合Q，存储未知最短距离的点；初始化起点的最短距离为0，其余点的最短距离为无穷大；重复执行以下步骤：从Q中选取距离起点最近的点u加入S中；对于u的每个邻居v，如果起点到v的距离比起点到u再加上u到v的距离更短，更新起点到v的距离；重复进行以上步骤，直到集合S包含所有点或者Q为空。

Floyd算法是一种动态规划算法，用于解决任意两点之间的最短路径问题，其核心思想是利用中间点的集合逐步缩小路径长度。具体实现过程为：创建一个二维数组dp，dp[i][j]表示i到j的最短路径长度；初始化dp[i][j]为i到j的边权或者无穷大；三重循环枚举所有点k，更新i到j的最短路径长度为dp[i][k]+dp[k][j]和dp[i][j]中的较小值；重复进行以上步骤，直到所有点两两之间的最短距离计算完毕。

上述两种算法的时间复杂度均为O(n^3)，其中n表示图中节点数。在实际应用中，Dijkstra算法适用于稠密图（边数接近于节点数平方），Floyd算法适用于稀疏图（边数远小于节点数平方）。