每组数据分为两个部分，第一部分为图的点数n，和边数m, 第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。

在这段代码中，输入的第一行应该是两个整数n和m，分别表示图的点数和边数。接下来的m行输入每条边的信息，每行包含三个整数，分别表示边的起点、终点和权值。你可以尝试以下输入格式：

6 9
0 1 10
0 2 3
1 2 5
1 3 1
2 3 8
2 4 2
2 5 4
3 4 7
4 5 6

这代表了一个有6个节点和9条边的无向图，每条边的信息依次为(0,1,10)，(0,2,3)，(1,2,5)，(1,3,1)，(2,3,8)，(2,4,2)，(2,5,4)，(3,4,7)，(4,5,6)。

相关问题

使用Prim算法求图的最小生成树(MST) 输入 每组数据分为两个部分，第一部分为图的点数n，和边数m, 第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。 输出 最小生成树，输出时按照边的两个端点的升序输出。（先看左端点，再看右端点，端点不换位置） 样例输入 Copy 3 3 0 1 10 0 2 15 1 2 50 样例输出 Copy 0 1 10 0 2 15

下面是使用Java实现Prim算法求解最小生成树的代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt(); // 点的个数
            int m = scanner.nextInt(); // 边的个数
            int[][] graph = new int[n][n]; // 邻接矩阵存储图
            for (int i = 0; i < m; i++) {
                int u = scanner.nextInt();
                int v = scanner.nextInt();
                int w = scanner.nextInt();
                graph[u][v] = w;
                graph[v][u] = w;
            }
            prim(graph);
        }
        scanner.close();
    }

    private static void prim(int[][] graph) {
        int n = graph.length;
        int[] dist = new int[n]; // 存储从当前最小生成树到各个点的最小距离
        int[] parent = new int[n]; // 存储最小生成树上每个点的父节点
        boolean[] visited = new boolean[n]; // 标记每个点是否已加入最小生成树
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(parent, -1);
        dist[0] = 0; // 从第一个点开始构建最小生成树
        for (int i = 0; i < n - 1; i++) {
            int u = getMinVertex(dist, visited);
            visited[u] = true;
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && !visited[v] && graph[u][v] < dist[v]) {
                    parent[v] = u;
                    dist[v] = graph[u][v];
                }
            }
        }
        printMST(parent, graph);
    }

    private static int getMinVertex(int[] dist, boolean[] visited) {
        int minDist = Integer.MAX_VALUE;
        int minVertex = -1;
        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minVertex = i;
            }
        }
        return minVertex;
    }

    private static void printMST(int[] parent, int[][] graph) {
        for (int i = 1; i < graph.length; i++) {
            if (parent[i] < i) {
                System.out.println(parent[i] + " " + i + " " + graph[parent[i]][i]);
            } else {
                System.out.println(i + " " + parent[i] + " " + graph[parent[i]][i]);
            }
        }
    }
}

对于输入`3 3 0 1 10 0 2 15 1 2 50`，程序将输出`0 1 10`和`0 2 15`，与样例输出一致。

求起始点1到N的最短路径.多组测试数据，对于每组数据 第一行是两个整数N， M。分别代表定点的数个和边的关系的个数。 从第二行至M+1行，每行三个整数，start, end, value。代表，节点start，节点end之间有一条长度为value的无向边。求1到N的最短路径。 (M, N, start, end, value < 100)对于每组测试数据，输出一个整数result，代表1至N的最短路径的value。

这道题可以使用 Dijkstra 算法求解。具体步骤如下：

1. 初始化距离数组 dist[]，将起点到每个顶点的距离设为无穷大，起点到自己的距离设为 0。

2. 创建一个集合 visited，用于记录已经确定最短路径的顶点。

3. 从起点开始，依次遍历与起点相邻的每个顶点，更新它们的距离。具体操作如下：

a. 选择一个距离起点最短的未确定最短路径的顶点 u。

b. 将顶点 u 加入 visited 集合中。

c. 遍历与顶点 u 相邻的每个顶点 v，更新 v 的距离。如果新的距离比原来的距离小，则更新 dist[v] 的值。

4. 重复步骤 3 直到所有顶点的最短路径都被确定。

5. 最终，dist[] 数组中存储的就是起点到每个顶点的最短路径长度。

需要注意的是，Dijkstra 算法只适用于没有负权边的图。如果图中存在负权边，可以考虑使用 Bellman-Ford 算法或 Floyd 算法。

以下是 Python 代码实现：

import heapq

INF = 0x3f3f3f3f

def dijkstra(graph, start, end):
    n = len(graph)
    dist = [INF] * n
    visited = set()
    heap = [(0, start)]
    dist[start] = 0
    while heap:
        (d, u) = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist[end]

if __name__ == '__main__':
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break
        graph = [[] for _ in range(n)]
        for _ in range(m):
            start, end, value = map(int, input().split())
            graph[start-1].append((end-1, value))
            graph[end-1].append((start-1, value))
        result = dijkstra(graph, 0, n-1)
        print(result)

时间复杂度为 O(mlogn)，其中 n 和 m 分别为顶点数和边数。