奇怪的连通图

题目描述：

已知一个无向带权图，求最小整数k。使仅使用权值小于等于k的边，节点1可以与节点n连通。

 

输入：

输入包含多组测试用例，每组测试用例的开头为一个整数n(1 <= n <= 10000)，m(1 <= m <= 100000)，代表该带权图的顶点个数，和边的个数。
接下去m行，描述图上边的信息，包括三个整数,a(1 <= a <= n),b(1 <= b <= n),c(1 <= c <= 1000000),表示连接顶点a和顶点b的无向边，其权值为c。

 

输出：

输出为一个整数k，若找不到一个整数满足条件，则输出-1。

 

样例输入：

3 31 3 51 2 32 3 23 21 2 32 3 53 11 2 3 

样例输出：

35-1

Source Code:

#include <cstdio>#include <algorithm> using namespace std; struct Edge{    int start;    int end;    int cost;}; Edge edgeArr[100010];int Root[10010]; void initRoot(int length){    for(int i=1;i<=length;++i)        Root[i]=-1;} bool cmp(Edge a,Edge b){    return a.cost<=b.cost;} int findRoot(int x){    if(Root[x]==-1)        return x;    else{        int tmp=findRoot(Root[x]);        Root[x]=tmp;        return tmp;    }} int main(){    int n,m;    while(scanf("%d%d",&n,&m)!=EOF){        initRoot(n);        for(int index=1;index<=m;++index){            scanf("%d",&edgeArr[index].start);            scanf("%d",&edgeArr[index].end);            scanf("%d",&edgeArr[index].cost);        }        sort(edgeArr+1,edgeArr+m+1,cmp);        int answer=-1;        for(int index=1;index<=m;++index){            int Root_a=findRoot(edgeArr[index].start);            int Root_b=findRoot(edgeArr[index].end);            if(Root_a!=Root_b){                Root[Root_a]=Root_b;                if(edgeArr[index].cost>=answer)                    answer=edgeArr[index].cost;            }            if(findRoot(1)==findRoot(n)){                break;            }        }        if(findRoot(1)!=findRoot(n))            printf("%d\n",-1);        else            printf("%d\n",answer);    }    return 0;}/**************************************************************    Problem: 1545    User: lcyvino    Language: C++    Result: Accepted    Time:770 ms    Memory:2232 kb****************************************************************/

 

题目1545：奇怪的连通图