====== 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 pq = new PriorityQueue (g.N, new Comparator() { @Override public int compare(Integer n1, Integer n2) { if( dist[n1] < dist[n2] ) return -1; if( dist[n1] > dist[n2] ) return 1; return 0; } } ); pq.add(start); 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; pq.add(neigh); } 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 pq = new PriorityQueue (g.N, new Comparator() { @Override public int compare(Integer n1, Integer n2) { if( dist[n1] < dist[n2] ) return -1; if( dist[n1] > dist[n2] ) return 1; return 0; } } ); pq.add(start); 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; pq.add(neigh); } 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 #define FOR(A, B) for(int (A) = 0; (A) < (B); (A)++) #define pb push_back #define mp make_pair using namespace std; pair edges[5555*5554/2]; int meaningful[5555]; int wedges[5555][5555]; vector< vector > 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 > besties; sort(edges, edges+m); FOR(i, n) paths.pb(vector()); 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; }