fork(1) download 
  1. #include <bits/stdc++.h>
  2. #define pii pair<int, int>
  3. #define piii pair<int,pii>
  4. #define f first
  5. #define s second
  6. using namespace std;
  7.  
  8. vector<piii> edges;
  9. int par[107];
  10.  
  11. void reset( int n )
  12. {
  13.     for( int i=1; i<=n; i++ )
  14.         par[i]= i;
  15. }
  16.  
  17. int Find( int u )
  18. {
  19.     if( par[u]==u )
  20.         return u;
  21.     return par[u]= Find( par[u] );
  22. }
  23.  
  24. void unite( int u, int v )
  25. {
  26.     int paru= Find( u );
  27.     int parv= Find( v );
  28.  
  29.     if( paru!=parv )
  30.         par[paru]= parv;
  31. }
  32.  
  33. int main()
  34. {
  35.     int n,m;
  36.  
  37.     while( scanf("%d %d", &n, &m)==2 and (n+m) )
  38.     {
  39.         for( int i=0; i<m; i++ )
  40.         {
  41.             int p,q,w;
  42.             scanf("%d %d %d", &p, &q, &w);
  43.  
  44.             edges.push_back( piii( w, pii( p,q ) ) );
  45.         }
  46.  
  47.         sort( edges.begin(), edges.end() );
  48.  
  49.         int diff= 1e9;
  50.  
  51.         for( int i=0; i<m; i++ )
  52.         {
  53.             if( m-i<n-1 )
  54.                 break;
  55.             reset(n);
  56.             vector<bool> vis( n+1,0 );
  57.             int cnt= 0;
  58.  
  59.             int mx= -1e9, mn= 1e9, thisdiff= 0;
  60.  
  61.             for( int j=i; j<m; j++ )
  62.             {
  63.                 int u= edges[j].s.f;
  64.                 int v= edges[j].s.s;
  65.  
  66.                 if( !vis[u] )
  67.                     vis[u]= 1;
  68.                 if( !vis[v] )
  69.                     vis[v]= 1;
  70.  
  71.                 if( Find(u)!=Find(v) )
  72.                 {
  73.                     unite(u,v);
  74.                     mn= min( mn, edges[j].f );
  75.                     mx= max( mx, edges[j].f );
  76.                 }
  77.             }
  78.  
  79.             thisdiff= mx-mn;
  80.             bool f= 1;
  81.  
  82.             for( int i=1; i<=n; i++ )
  83.             {
  84.                 if(!vis[i])
  85.                 {
  86.                     f= 0;
  87.                     break;
  88.                 }
  89.  
  90.                 if( vis[i] and Find(i)==i )
  91.                     cnt++;
  92.             }
  93.  
  94.             if( f and cnt==1 )
  95.                 diff= min( diff, thisdiff );
  96.         }
  97.  
  98.         if(diff==1e9)
  99.             diff= -1;
  100.  
  101.         printf("%d\n", diff);
  102.  
  103.         edges.clear();
  104.     }
  105. }
  106.  
Success #stdin #stdout 0s 4520KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/m5o0ut
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!