Java program for the above approach
import java . util . * ; class GFG { static int maxindex ( int [ ] dist , int n ) { int mi = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( dist [ i ] > dist [ mi ] ) mi = i ; } return mi ; } static void selectKcities ( int n , int weights [ ] [ ] , int k ) { int [ ] dist = new int [ n ] ; ArrayList < Integer > centers = new ArrayList < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { dist [ i ] = Integer . MAX_VALUE ; }