fork(1) download
copy 
  1. #include<iostream>
  2. //#include<conio.h>
  3. #include<algorithm>
  4. #include<vector>
  5. #include<list>
  6. using namespace std;
  7. struct edge
  8. {
  9.     int u;
  10.     int v;
  11.     int w;
  12. }arr[500000];
  13.  
  14. inline int comp(struct edge a,struct edge b)
  15. {
  16.     return (a.w>b.w);
  17. }  
  18. int p[1005];
  19. int rank[1005];      
  20.  
  21. inline int  makeset(int x)
  22. {
  23.     p[x]=x;
  24.     rank[x]=0;
  25. }    
  26. int root;
  27. inline int findset(int x)
  28. {
  29.     if(x!=p[x])
  30.    { p[x]=findset(p[x]);p[x];}
  31.     return (p[x]);
  32. }   
  33.  
  34. inline void linkset(int x,int y)
  35. {
  36.     if(rank[x]>rank[y])
  37.     p[y]=x;
  38.     else
  39.     p[x]=y;
  40.     if(rank[x]==rank[y])
  41.     rank[y]=rank[y]+1;
  42. }  
  43.  
  44. inline void unionset(int x,int y)
  45. {
  46.     linkset(findset(x),findset(y));
  47. }    
  48.  
  49.   vector<int> d;
  50.  
  51. int sum=100000019;
  52. vector<int> sum1[500000];
  53. inline void dfs(int a,int b)
  54. {
  55.     while(b!=p[b])
  56.     {
  57.         if(sum>sum1[a][p[b]])
  58.         {sum=sum1[a][p[b]];sum1[a][p[b]]=sum;sum1[p[b]][a]=sum;
  59.  
  60.         }
  61.  
  62.  
  63.         b=p[b];
  64.     }
  65. }        
  66.  
  67.  
  68.  
  69.  
  70.  
  71. int main()
  72. {
  73.     int n,e,t,a,b,c,i,j,k,l;
  74.     scanf("%d%d",&n,&e);
  75.     for(i=0;i<e;i++)
  76.     scanf("%d%d%d",&arr[i].u,&arr[i].v,&arr[i].w);
  77.  
  78.     sort(arr,arr+e,comp);
  79.      int visited[n+1];
  80.     int visit[n+1];
  81.  
  82.      for(i=0;i<n;i++){p[i]=i;visited[i]=0;visit[i]=0; makeset(i);}
  83.  
  84.  //   for(i=0;i<e;i++)
  85.   //  printf("%d%d%d\n",arr[i].u,arr[i].v,arr[i].w);
  86.  
  87.  
  88.  
  89.    int x,y;
  90.    for(i=0;i<e;i++)
  91.    {
  92.  
  93.        x=findset(arr[i].u);
  94.        y=findset(arr[i].v);
  95.        if(x!=y)
  96.        {
  97.            if(arr[i].u>arr[i].v)
  98.  
  99.        {  for(l=0;l<=arr[i].u;l++)
  100.          { sum1[x].push_back(100000009);
  101.            sum1[y].push_back(100000009);
  102.            sum1[arr[i].u].push_back(100000009);
  103.              sum1[arr[i].v].push_back(100000009);
  104.          }
  105.        }   
  106.         else  
  107.         {
  108.               for(l=0;l<=arr[i].v;l++)
  109.           {  
  110.            sum1[x].push_back(100000009);
  111.            sum1[y].push_back(100000009); 
  112.            sum1[arr[i].u].push_back(100000009);
  113.              sum1[arr[i].v].push_back(100000009);
  114.            }
  115.           } 
  116.             unionset(x,y);
  117.  
  118.           sum1[x][y]=arr[i].w;
  119.           sum1[y][x]=arr[i].w;
  120.          //  printf("x   %d  y %d    sum[x][y]    %d\n",x,y,sum1[x][y]);
  121.  
  122.           if(visit[arr[i].u]==0)
  123.            d.push_back(arr[i].u);
  124.            if(visit[arr[i].v]==0)
  125.            d.push_back(arr[i].v);
  126.            visit[arr[i].u]=1;
  127.            visit[arr[i].v]=1;
  128.  
  129.  
  130.  
  131.  
  132.        }     
  133.  
  134.      }     
  135. // for(i=0;i<e;i++)printf("hi   %d\n",d[i]) ;   
  136.  
  137. for(i=0;i<n;i++)
  138. dfs(i,i);   
  139.  
  140.  int root=findset(0);   
  141.  
  142.  
  143. //printf("root   %d   \n",findset(0)); 
  144. //printf("root   %d   \n",findset(2));
  145. //printf("root   %d   \n",findset(3));  
  146.  
  147.  
  148. //printf("asdas  %d\n",sum1[0][2]);
  149.  
  150. for(i=0;i<n;i++)
  151. {for(j=0;j<n;j++)
  152. {       
  153. int sum2=100000019;   
  154. int sum3=100000019;
  155.    if(i==j)printf("0 ");
  156.  
  157.        else if(sum1[i][j]==100000009)
  158.           { //printf("viaksh   %d  %d\n",i,j);
  159.               int r=i,s=j;
  160.                   while(r!=p[r])
  161.                 {
  162.                     if(sum2>sum1[r][p[r]])
  163.                     sum2=sum1[r][p[r]];
  164.                   //   printf("mayank  r    %d  p[r]   %d    sum1[r][p[r]]%d\n",r,p[r],sum1[r][p[r]]);
  165.                     r=p[r];  
  166.  
  167.  
  168.                 }
  169.                      while(s!=p[s])
  170.                 {
  171.                     if(sum3>sum1[p[s]][s])
  172.                   {  sum3=sum1[p[s]][s];
  173.                   }  //printf("churu p[s]  %d  s  %d sum   %d\n",p[s],s,sum1[p[s]][s]);
  174.                     s=p[s];  
  175.  
  176.  
  177.                 }
  178.                 if(sum2>sum3)
  179.                 printf("%d ",sum3);
  180.                 else
  181.                 printf("%d ",sum2);  
  182.  
  183.         }
  184.         else          
  185.       printf("%d ",sum1[i][j]);    
  186.  
  187.          }  
  188.  
  189.  
  190.          printf("\n");
  191.  }    
  192. //system("pause");
  193.    return 0;
  194.     // getch();
  195.  }            
  196.  
Success #stdin #stdout 0s 14600KB
comments (?)
stdin
copy 
3 3
0 1 1
1 2 2
0 2 3
stdout
copy 
0 2 3 
2 0 2 
3 2 0
https://ideone.com/H4Vo97
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

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!