===== Long slopes =====

**Zadání**\\
Viz odkaz:  [[https://cw.felk.cvut.cz/courses/a4b33alg/getdata.php?task=longslopes2&item=descc.html|Dlouhé sjezdovky]].\\


=== Nejrychlejší řešení v Javě ===

<code C>
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

/**
 * ======================================================
 * ONE END OF THE SLOPE
 * MAY CONTAIN SEVERAL PATHS DOWNHILL
 * ======================================================
 */
class CheckPoint {	
	ArrayList<Integer> whereTo;	
	int[] costTo;
	
	public CheckPoint(int points) {
		whereTo = new ArrayList<Integer>();		
		costTo = new int[points];
	}
	
	public void add(int to, int cost) {				
		whereTo.add(to);
		costTo[to] = cost;
	}
	
	public int costTo(int to) {		
		return costTo[to];
	}
}
// ------------------------------------------------------

/**
 * ======================================================
 * ONE SLOPE - LEADING FROM POINT TO POINT
 * ======================================================
 */
class OneSlope implements Comparable<OneSlope> {
	int from;
	int to;	
	
	public OneSlope(int from, int to) {
		this.from = from;
		this.to = to;		
	}

	@Override
	public int compareTo(OneSlope obj) {
		return this.from -  obj.from; 		
	}	
}
//------------------------------------------------------

/**
 * ======================================================
 * SOLVER
 * - LOADS DATA
 * - GOES THROUGH THE SLOPES AND FINDS THE BEST ONE(S)
 * ======================================================
 */
class Solver {
	
	int points;
	int slopes;
	CheckPoint[] allPoints;
	
	int[] fromPoint;
	int[] toPoint;
	
	ArrayDeque<Integer> rFrom;
	ArrayDeque<Integer> rTo;
	int maxLen;	

	public void solve() {
		loadData();
		goThroughSlopes();
		printResult();	
	}
	
	private void loadData() {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine());
			points = Integer.parseInt(st.nextToken());
			slopes = Integer.parseInt(st.nextToken());

			allPoints = new CheckPoint[points];
			fromPoint = new int[slopes];
			toPoint = new int[slopes];			
			rFrom = new ArrayDeque<Integer>();
			rTo = new ArrayDeque<Integer>();
			maxLen = 0;

			// Init
			for (int i = 0; i < points; i++) {
				allPoints[i] = new CheckPoint(points);
			}

			// Load all of the slopes
			for (int i = 0; i < slopes; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				int cost = Integer.parseInt(st.nextToken());

				allPoints[from].add(to, cost);
				fromPoint[i] = from;
				toPoint[i] = to;
			}
			
			// Sort slopes from points for better pruning
			for (int i = 0; i < points; i++) {
				Collections.sort(allPoints[i].whereTo);
			}

		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private void goThroughSlopes() {
		for (int i = 0; i < slopes; i++) {
			fixIt(fromPoint[i], toPoint[i]);
		}
	}
	
	private void fixIt(int from, int to) {
		int[] arr = new int[to - from];

		// First step - go through slopes from starting point
		for (Integer track : allPoints[from].whereTo) {
			if (track > to)
				break;
			arr[track - from - 1] = allPoints[from].costTo(track);
		}

		// Second step - go through points between starting and ending point
		// and see if there is slope that leads nearer to the ending point 
		// and is longer than the one found earlier in this method
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == 0)
				continue;

			for (Integer track : allPoints[i + from + 1].whereTo) {
				if (track > to)
					break;
				int cost = allPoints[i + from + 1].costTo(track) + arr[i];
				if (arr[track - from - 1] < cost)
					arr[track - from - 1] = cost;
			}
		}

		// Compare the length with the best so far found
		if (arr[arr.length - 1] > maxLen) {			
			rFrom.clear(); rTo.clear();
			rFrom.add(from); rTo.add(to);
			maxLen = arr[arr.length - 1];
		} else if (arr[arr.length - 1] == maxLen) {
			rFrom.add(from); rTo.add(to);
		}
	}
	
	private void printResult() {
		ArrayDeque<OneSlope> result = new ArrayDeque<OneSlope>();
		
		while(!rFrom.isEmpty()) {
			result.add(new OneSlope(rFrom.pop(), rTo.pop()));
		}		
		
		Object[] ar = result.toArray();
		Arrays.sort(ar); // Sort the best slopes
		for (Object sl : ar) {
			OneSlope os = (OneSlope) sl;
			System.out.println(os.from + " " + os.to); // print solution
		}	
	}	
	
}
//------------------------------------------------------


/**
 * ======================================================
 * MAIN CLASS
 * CALLS SOLVER TO SOLVE THE PROBLEM
 * ======================================================
 */
public class Main {
	
	public static void main(String[] args) {
		Solver solver = new Solver();
		solver.solve();
	}
}
</code>


=== Nejrychlejší  řešení v C/C++ ===

<code C>
#include <stdio.h>
#include <stdlib.h>

typedef struct slopes {
    int count;
    short * tos;
    int * prices;
} slopes;

typedef struct result {
    short start;
    short end;
} result;

int n, m, max = 0, res_count = 0;
slopes **slps;
result **res;

int **longest_paths;

void add_to_res(short start, short end) {
    if(res_count < 10) {
        res[res_count]->start = start;
        res[res_count]->end = end;
        res_count++;
    }
}

int main() {

    scanf("%i %i", &n, &m);
    slps = malloc(n*sizeof(slopes*));
    res = malloc(10*sizeof(result*));
    res[0] = malloc(sizeof(result));
    res[1] = malloc(sizeof(result));
    res[2] = malloc(sizeof(result));
    res[3] = malloc(sizeof(result));
    res[4] = malloc(sizeof(result));
    res[5] = malloc(sizeof(result));
    res[6] = malloc(sizeof(result));
    res[7] = malloc(sizeof(result));
    res[8] = malloc(sizeof(result));
    res[9] = malloc(sizeof(result));

    longest_paths = malloc(n*sizeof(int*));
    
    int i, j, k;

    for(i = 0; i<n; i++) {
        longest_paths[i] = calloc(n, sizeof(int));
        slps[i] = malloc(sizeof(slopes));
        slps[i]->count = 0;
        slps[i]->tos = malloc((n-i)*sizeof(short));
        slps[i]->prices = malloc((n-i)*sizeof(int));
    }

    for(i = 0; i<m; i++) {
        short a,b,c;
        scanf("%hi %hi %hi", &a, &b, &c);
        slps[a]->tos[slps[a]->count] = b;
        slps[a]->prices[slps[a]->count] = c;
        slps[a]->count++;
    }

    for(i = n-1; i>=0; i--) {
        for(j = 0; j<slps[i]->count; j++) {
            short tmp = slps[i]->tos[j];
            if(longest_paths[i][tmp] < slps[i]->prices[j])
                longest_paths[i][tmp] = slps[i]->prices[j];
            for(k = i; k<n; k++) {
                if(longest_paths[tmp][k] > 0 && slps[i]->prices[j]+longest_paths[tmp][k] > longest_paths[i][k]) {
                    longest_paths[i][k] = slps[i]->prices[j]+longest_paths[tmp][k];
                }
            }
        }
    }

    for(i = 0; i<n; i++) {
        for(j = 0; j<slps[i]->count; j++) {
            short tmp = slps[i]->tos[j];
            int length = longest_paths[i][tmp];
            if(length > max) {
                max = length;
                res_count = 0;
                add_to_res(i, tmp);
            } else if (length == max) {
                add_to_res(i, tmp);
            }
        }
    }
   
    for(i = 0; i<res_count; i++) {
        printf("%hi %hi\n", res[i]->start, res[i]->end);
    }

    return 0;
}
</code>