CODEVS 1001 舒适的路线

思路:先按照速度大小对边排序,再枚举最终路径中的速度最大值,并查集,更新答案

 #include<iostream>
 #include<vector>
 #include<algorithm>
 using namespace std;
 +;
 struct BCJ{
     int fa[maxn],n;
     void init(int n){
         this->n=n;
         ;i<=n;i++) fa[i]=i;
     }
     int find(int x){
         if(fa[x]==x) return x;
         return fa[x]=find(fa[x]);
     }
     bool Judge(int a,int b){
         return find(a)==find(b);
     }
     void Union(int a,int b){
         if(find(a)!=find(b)){
             fa[find(a)]=find(b);
         }
     }
 };
 struct Edge{
     int from,to,dist;
     bool operator<(const Edge& b)const{
         return dist<b.dist;
     }
 };
 int gcd(int a,int b){
     ?a:gcd(b,a%b);
 }
 BCJ bcj;
 vector<Edge> e;
 ,b=-;
 int main()
 {
     int f,t,d;
     cin>>N>>M;
     ;i<M;i++){
         cin>>f>>t>>d;
         e.push_back((Edge){f,t,d});
     }
     cin>>S>>T;
     sort(e.begin(),e.end());
     ;i<e.size();i++)
     {
         bcj.init(N);
         ;j--){
             if(!bcj.Judge(e[j].from,e[j].to)){
                 bcj.Union(e[j].from,e[j].to);
                 if(bcj.Judge(S,T)){
                     &&b==-) a=e[i].dist,b=e[j].dist;
                     else if(a*e[j].dist>b*e[i].dist) a=e[i].dist,b=e[j].dist;
                     break;
                 }
             }
         }
     }
     &&b==-) cout<<"IMPOSSIBLE";
     else{
         cout<<a/gcd(a,b);
         ) cout<<'/'<<b/gcd(a,b);
     }
     ;
 }
上一篇:Javascript 常用函数【2】


下一篇:TOP100summit:【分享实录】Twitter 新一代实时计算平台Heron