Graph

Graph
( graph .cpp/c/pas)
Description
小 Y 又开始了一段旅途。
这次，他要经过一个图，从1号点到达n号点，每个点设有休息站。
小 Y 计划用最多k天走完全程，除第k天外，每一天小 Y 都必须在休息站过夜。所以，一段路必须在同一天走完。
小 Y 的体力有限，他希望走的路程最大的一天中走的路尽可能少，请求出这个最小值。
Input
第一行三个整数n、m、k表示图的顶点数、边数、天数。
从第二行开始，之后的m行，每行三个整数ui、vi、wi表示从ui和vi间有一条双向道路，长度为wi。
Output
一行一个正整数，如果小 Y 能走完全程，输出走的路程最大的一天中走的路程最小值，否则输出-1。
Example
graph.in
3 2 4
3 2 4
1 2 1
graph.out
4
附加样例见选手目录下『graph』文件夹。
Hint
对于10%的数据,m=0；
对于30%的数据,n,m,k<=10 ；
对于100%的数据,2<=n<=k<=7500,0<=m<=200000,1<=wi<=10^9；
保证没有重边和自环。

 【题目分析】

 开始想的是用dijkstra，算一下时间应该不会超（我觉得....），但据说空间会爆？

好吧，正解思路：并查集+二分答案，先找到最大的边权值为右端点，然后二分查找，去掉比找到的答案大的边

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node{
    int T,T1,T2;
}a[200001];
int m,n,k,ans=-1,F[7501];
int Find(int t)
{
    if (F[t]==t)
      return t;
    return F[t]=Find(F[t]);
}
bool Check(int t)
{
    for (int i=1;i<=n;i++)
      F[i]=i;
    for (int i=1;i<=m;i++)
    {
          if (a[i].T>t)
            continue;
          int t1=Find(a[i].T1);
          int t2=Find(a[i].T2);
          if (t1!=t2)
            F[t2]=t1;
          if (Find(1)==Find(n))
            return true;
    }
    return false;
}
int main()
{
    //freopen("graph.in","r",stdin);
    //freopen("graph.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    int maxn=0;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].T1,&a[i].T2,&a[i].T);
        maxn=max(maxn,a[i].T);
    }
    int Left=0,Right=maxn;
    while (Left<=Right)
    {
        int Mid=(Left+Right)>>1;
        if (Check(Mid))
        {
            ans=Mid;
            Right=Mid-1;
        }
        else
          Left=Mid+1;
    }
    printf("%d",ans);
    return 0;
}