fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define OO 0x3f3f3f3f
  4. inline int SD(){int i ;scanf("%d", &i);return i;}
  5. inline char SC(){char i;scanf(" %c", &i);return i;}
  6. const int AKA = 1e6 + 6 , N = 1e3+4;
  7. int adjmat[N][N] , n , m , k;
  8. void init()
  9. {
  10.     for (int i = 1; i <= n; i++)
  11.     {
  12.         for (int j = 1; j <= n; j++)
  13.             adjmat[i][j] = OO;
  14.         adjmat[i][i] = 0;
  15.     }
  16. }
  17. int main()
  18. {
  19.     n = SD() , m = SD() , k = SD();
  20.     init();
  21. 	for(int i = 1;i <= m;i++)
  22.     {
  23.         int a = SD() , b = SD() , v = SD();
  24. 		adjmat[a][b] = adjmat[b][a] = v;
  25. 	}
  26.  
  27. 	for(int k = 1;k <= n;k++)
  28. 		for(int i=1;i<= n;i++)
  29. 			for(int j=1;j<= n;j++)
  30. 				adjmat[i][j]=min(adjmat[i][j],adjmat[i][k]+adjmat[k][j]);
  31.     vector<int> ans;
  32. 	for (int i = 1; i <= n; i++)
  33.         for (int j = i + 1; j <= n; j++)
  34.         {
  35.             if(adjmat[i][j] != OO  && adjmat[i][j])
  36.                 //printf("APSP(%d, %d) = %d\n", i , j , adjmat[i][j]);
  37.                 ans.push_back(adjmat[i][j]);
  38.         }
  39.     sort(ans.begin() , ans.end());
  40.     for(int i = 0 ; i < ans.size() ; ++i)
  41.         printf("%d " , ans[i]);
  42.  
  43. }
  44.  
Success #stdin #stdout 0s 4292KB
comments (?)
stdin
copy 
6 10 5
2 5 1
5 3 9
6 2 2
1 3 1
5 1 8
6 5 10
1 6 5
6 4 6
3 6 2
3 4 5
stdout
copy 
1 1 2 2 3 3 4 5 5 5 6 6 6 8 9
https://ideone.com/DxeN2z
language:
C++ (gcc 8.3)
created:
4 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!