Warning

# 1. MST and Dijkstra


// MST and Dijkstra compared
// Note the sort method in Kruskal alg.

import java.util.*;
import java.io.*;

public class Solvers {

static void dijkstraNsquared(Graph g, int start,  final int [] dist, int [] pred ) {
int INF = Integer.MAX_VALUE;
int currnode = start, currdist, neigh;
boolean [] closed = new boolean [g.N];

for(int i = 0; i < g.N; i++) pred[i] = i;
Arrays.fill(dist, INF);
Arrays.fill(closed, false);
dist[start] = 0;

for( int i = 0; i < g.N; i++ ){
// find the closest node
currdist = INF;
for( int j = 0; j < g.N; j++)
if( !closed[j] && dist[j] < currdist ){
currdist = dist[j];
currnode = j;
}

// expand the closest node and close it
for( int j = 0; j < g.dg[currnode]; j++ ){
neigh = g.edge[currnode][j];
if( !closed[neigh] && ( dist[neigh] > dist[currnode] + g.w[currnode][j]) ) {
dist[neigh] = dist[currnode] + g.w[currnode][j];
pred[neigh] = currnode;
}
closed[currnode] = true;
}
} // for N steps
}

public static void dijkstraElogN(Graph g, int start, final int [] dist, int [] pred ) {
int currnode = start, currdist, neigh;
int INF = Integer.MAX_VALUE;
boolean [] closed = new boolean[g.N];

PriorityQueue <Integer> pq
= new PriorityQueue<Integer> (g.N,
new Comparator<Integer>() {
@Override
public int compare(Integer n1, Integer n2) {
if( dist[n1] < dist[n2] ) return -1;
if( dist[n1] > dist[n2] ) return 1;
return 0;
}
}
);

for(int i = 0; i < g.N; i++) pred[i] = i;
Arrays.fill(dist, INF);
Arrays.fill(closed, false);
dist[start] = 0;

for(int i = 0; i < g.N; i++) {
// take the closest node
while( closed[currnode = pq.poll()] == true );
// and expand it
for( int j = 0; j < g.dg[currnode]; j++ ){
neigh = g.edge[currnode][j];
if( !closed[neigh] && ( dist[neigh] > dist[currnode] + g.w[currnode][j]) ) {
dist[neigh] = dist[currnode] + g.w[currnode][j];
pred[neigh] = currnode;
}
closed[currnode] = true;
}
}
}

static void MST_Nsquared(Graph g, int start,  final int [] dist, int [] pred ) {
int INF = Integer.MAX_VALUE;
int currnode = start, currdist, neigh;
boolean [] closed = new boolean [g.N];

for(int i = 0; i < g.N; i++) pred[i] = i;
Arrays.fill(dist, INF);
Arrays.fill(closed, false);
dist[start] = 0;

for( int i = 0; i < g.N; i++ ){
// find the closest node
currdist = INF;
for( int j = 0; j < g.N; j++)
if( !closed[j] && dist[j] < currdist ){
currdist = dist[j];
currnode = j;
}

// expand the closest node and close it
for( int j = 0; j < g.dg[currnode]; j++ ){
neigh = g.edge[currnode][j];
if( !closed[neigh] && ( dist[neigh] > g.w[currnode][j]) ) {
dist[neigh] = g.w[currnode][j];
pred[neigh] = currnode;
}
closed[currnode] = true;
}
} // for N steps
}

public static void MST_ElogN(Graph g, int start, final int [] dist, int [] pred ) {
int currnode = start, currdist, neigh;
int INF = Integer.MAX_VALUE;
boolean [] closed = new boolean[g.N];

PriorityQueue <Integer> pq
= new PriorityQueue<Integer> (g.N,
new Comparator<Integer>() {
@Override
public int compare(Integer n1, Integer n2) {
if( dist[n1] < dist[n2] ) return -1;
if( dist[n1] > dist[n2] ) return 1;
return 0;
}
}
);

for(int i = 0; i < g.N; i++) pred[i] = i;
Arrays.fill(dist, INF);
Arrays.fill(closed, false);
dist[start] = 0;

for(int i = 0; i < g.N; i++) {
// take the closest node
while( closed[currnode = pq.poll()] == true );
// and expand it
for( int j = 0; j < g.dg[currnode]; j++ ){
neigh = g.edge[currnode][j];
if( !closed[neigh] && ( dist[neigh] > g.w[currnode][j]) ) {
dist[neigh] = g.w[currnode][j];
pred[neigh] = currnode;
}
closed[currnode] = true;
}
}
}

public static void MST_Kruskal(Graph g, int [] edgesMST ) {

// store edges in one arr and sort them
int [] edges = new int[g.M*3];
int k = 0;
for( int i = 0; i < g.N; i++ )
for( int j = 0; j < g.dg[i]; j++ ) {
if( i <  g.edge[i][j] ) {
edges[k++] = g.w[i][j];
edges[k++] = i;
edges[k++] = g.edge[i][j];
}
}
qSort3( edges, 0, edges.length-3 );

// construct the MST with UF
initUF( g.N );
int edgesCount = 0, set1, set2;
k = 0;
while( edgesCount < g.N-1 ){
set1 = UF_find(edges[k+1]); set2 = UF_find(edges[k+2]);
if( set1 != set2 ) {  // found an edge of MST
UF_union( set1, set2 );
edgesCount++;
edgesMST[edgesCount*2-2] = edges[k+1]; edgesMST[edgesCount*2-1] = edges[k+1] ;
}
k += 3;
}
}

public static void main( String[] args ) {
int [] p = {3, 10, 11, -3, 22, 25, 7, 33, 34, 4, 42, 43, 2, 56, 56 };
qSort3(p, 0, p.length-3);
list(p);

}

static void list (int [] a) {
for( int x : a )
System.out.printf("%2d ", x);
System.out.printf("\n");
}

static void qSort(double a[], int low, int high) {
int iL = low, iR = high;
double pivot = a[low];
double aux;
do {
while (a[iL] < pivot) iL++;
while (a[iR] > pivot) iR--;
if (iL < iR) {
//swap(a,iL, iR);
aux = a[iL]; a[iL] = a[iR]; a[iR] = aux;
iL++; iR--;
}
else
if (iL == iR) { iL++; iR--;}

} while( iL <= iR);

if (low < iR)  qSort(a, low, iR);
if (iL < high) qSort(a, iL, high);
}

// always points to i%3=0 elem which stores the key
static void qSort3(int a[], int low, int high) {
int iL = low, iR = high;
int pivot = a[low];
int aux;
do {
while (a[iL] < pivot) iL+=3;
while (a[iR] > pivot) iR-=3;
if (iL < iR) {
//swap(a,iL, iR);
for(int k = 0; k < 3; k++ )
{ aux = a[iL+k]; a[iL+k] = a[iR+k]; a[iR+k] = aux; }
iL+=3; iR-=3;
}
else
if (iL == iR) { iL+=3; iR-=3;}

} while( iL <= iR);

if (low < iR)  qSort3(a, low, iR);
if (iL < high) qSort3(a, iL, high);
}

// uf

static int [] sets;
static int [] sizes;
static int elem1;

static void initUF(int n) {
sets = new int [n];
sizes = new int [n];
for(int i = 0; i < n; i++) {
sets[i] = i;
sizes[i] = 1;
}
}

static void UF_union(int a, int b) {
//System.out.printf(" unioning %d %d \n", a, b);
if (sizes[b] > sizes[a]) {
sets[a] = b;
sizes[b] += sizes[a];
}
else {
sets[b] = a;
sizes[a] += sizes[b];
}
}

static int UF_find(int a) {
elem1 = a;
while (a != sets[a])
a = sets[a];
sets[elem1] = a;  // shorten the path
return a;
}

static void listSet(int a) {  // for debuggin purposes only
int finda = UF_find(a);
for(int i = 0; i < sets.length; i++)
if(UF_find(i) == finda)
System.out.printf("%d ", i);
System.out.printf("\n");
}

}

# 2. Longslopes short solution

//Petr Poliak o Longslopes:

include <bits/stdc++.h>
#define FOR(A, B) for(int (A) = 0; (A) < (B); (A)++)
#define pb push_back
#define mp make_pair

using namespace std;

pair<int,int> edges[5555*5554/2];
int meaningful[5555];
int wedges[5555][5555];
vector< vector<int> > paths;

int main() {
int n,m;
scanf("%d %d", &n, &m);
FOR(i, m) {
int a,b,c;
scanf("%d %d %d", &a, &b, &c);
if(meaningful[a] < b) meaningful[a] = b;
edges[i].first = a;
edges[i].second = b;
wedges[a][b] = c;
wedges[b][a] = c;
}
vector< pair<int, int> > besties;
sort(edges, edges+m);
FOR(i, n) paths.pb(vector<int>());
int maxx = 0, aclen;
FOR(i, m) {
paths[edges[i].second].pb(edges[i].first);
if (wedges[edges[i].first][edges[i].second] >= maxx) {
if (wedges[edges[i].first][edges[i].second] > maxx) {
maxx = wedges[edges[i].first][edges[i].second];
besties.clear();
}
besties.pb(mp(edges[i].first, edges[i].second));
}
for(int j = 0; j < paths[edges[i].first].size(); j++) {
int t = paths[edges[i].first][j];
if (edges[i].second > meaningful[t]) continue;
aclen = wedges[edges[i].first][edges[i].second] + wedges[edges[i].first][t];
if (aclen > wedges[edges[i].second][t]) {
if (wedges[edges[i].second][t] == 0) paths[edges[i].second].pb(t);
wedges[edges[i].second][t] = aclen;
if (wedges[t][edges[i].second] > 0) {
if (aclen >= maxx) {
if (aclen > maxx) {
besties.clear();
maxx = aclen;
}
besties.pb(mp(t, edges[i].second));
}
}
}
}
}
sort(besties.begin(), besties.end());
printf("%d %d\n", besties[0].first, besties[0].second);
for(int i = 1; i < besties.size(); i++) {
if(besties[i] != besties[i-1])
printf("%d %d\n", besties[i].first, besties[i].second);
}
return 0;
}