Submit | All submissions | Best solutions | Back to list |
REITER - Optimale Reiseroute für Ritter |
Bei dieser Aufgabe versetzen wir uns zurück ins Mittelalter, als es noch Ritter gab. Eine der wesentlichen Tätigkeiten eines Ritters ist es, an Turnieren teilzunehmen. Bei einem typischen Turnier müssen die Ritter in Disziplinen wie Schwertkampf, Bogenschießen und verschiedenen Reitkämpfen gegeneinander antreten. Natürlich braucht jeder Ritter für die Reitkämpfe sein eigenes Pferd.
Leider braucht ein Ritter oft mehrere Tage, um von seiner Burg zu dem Ort zu gelangen, an dem das Turnier stattfinden soll. Und Pferde können ziemlich störrisch sein; so kann es vorkommen, dass das Pferd nach einer bestimmten Entfernung stehenbleibt und erst am nächsten Tag wieder weitergeht. Da der Ritter nicht mitten auf dem Land übernachten will, plant er die Reiseroute zum Turnier so, dass die maximale Tagesstrecke, die er mit seinem Pferd zurücklegt, möglichst gering ist. Daher ist eine lange Reiseroute, die viele Tage mit kurzen Tagesstrecken beinhaltet, besser als eine kurze Reiseroute mit einer langen Tagesstrecke.
Schreiben Sie ein Programm, dass eine optimale Reiseroute für einen Ritter findet, d. h. eine Reiseroute, bei der die maximale Tagesstrecke der Reiseroute minimal ist.
Eingabe
Die erste Zeile der Eingabe enthält die Anzahl n an möglichen Übernachtungsorten (2 ≤ n ≤ 10000). Die Übernachtungsorte werden mit Zahlen zwischen 1 und n benannt, wobei die Burg des Ritters mit 1 benannt wird, und der Ort des Turniers mit n.
Die zweite Zeile der Eingabe enthält die Anzahl an möglichen Tagesstrecken m (n-1 ≤ m ≤ 200000). Die folgenden m Zeilen enthalten jeweils drei natürliche Zahlen a b c, die die Tagesstrecken beschreiben, wobei a und b zwei unterschiedliche Orte bezeichnen, zwischen denen der Ritter reisen kann (sowohl von a nach b als auch andersherum), und c gibt die Distanz an (1 ≤ c ≤ 109).
Ausgabe
Die Ausgabe soll die Distanz der maximalen Tagesstrecke sein, die der Ritter zurücklegen muss, um den Turnierort zu erreichen. Sie können annehmen, dass immer mindestens eine Verbindung von der Ritterburg zum Turnierort existiert.
Beispiel
Eingabe: 6 7 1 2 5 2 3 1 3 6 1 1 4 4 4 6 4 1 5 5 6 5 7 Ausgabe: 4
Die optimale Verbindung ist hier 1 -> 4 -> 6
Added by: | Adrian Kuegel |
Date: | 2008-12-01 |
Time limit: | 1.869s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |
Resource: | ACM Southwestern European Regional Contest 2008 (http://www.swerc.eu) |