算法思路：dijkstra算法是把结点分为两个集合，一个是已经求出最短路的集合S，另一个就是其他结点的集合U，一开始S只有源结点V0，dijkstra算法就是不断的冲U集合中找出离中转点最近的点，然后把它加入到S集合中，加入后更新U集合的数据。 模拟一遍：一开始只有S只有v0源点，然后在U集合中找到了离v0最近的结点k，把k加入到S中，并把U中的结点数据更新。更新规则如下：if（dist[u]+map[u][j]<dist[j]) dist[j]=dist[u]+map[u][j] 其中dist[u]代表了v0到u的最短距离。map[u][j]表示u到j的距离。 具体代...

MST（Minimum Spanning Tree，最小生成树）问题有两种通用的解法，Prim算法就是其中之一，它是从点的方面考虑构建一颗MST，大致思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的...

Kruskal算法 1.概览 Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。 2.算法简单描述 1).记Graph中有v个顶点，e个边 2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边...

#include <stdio.h> #include <stdlib.h> int cmp(const void *a,const void *b) { return((int*)a)[1]-((int*)b)[1]; } int main() { int t,n,i,x1; int m[1005][2]; scanf("%d",&amp;t); for(i=1;i<=t;i++) { scanf("%d",&amp;n); ...