Search
Zadání Viz odkaz: Dlouhé sjezdovky.
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(); } }
#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; }