Titelgrafik.

Inhalt

Ergebnisse des 1. OWINF

Dies sind die Ergebnisse des 1. OWINF vom 8.10.2005:


fluss prim reise Total
Ludwig Schmidt 67 45 100 212
Christian Matt 36 75 70 181
Andreas Krueger 0 30 100 130
... 60 50
110
... 24 50 20 94
... 42 50
92
... 0 90
90
... 35 55
90
...
80
80
...
50 10 60
...
40 20 60
...
20 30 50
...
20
20
...
15
15
... 0 15 0 15
...


0
...


0
...


0
...


0
...


0
...


0
...


0
...


0
...


0

Vielen Dank an alle, die teilgenommen haben. Wir hoffen, daß es Euch Spaß gemacht hat. Die Aufgaben waren, wie man am Ergebnis leicht sieht, recht schwer. Auch jeder, der hier nicht namentlich erwähnt ist, findet sich ja selbst wieder.

Die ersten 12 Teilnehmer bekamen eine Urkunde zugeschickt, sofern sie auf unsere Mail geantwortet haben; die ersten drei Plätze erhielten Buchpreise.

Das OWINF-Team

Aufgaben und Musterlösungen

Bäuerchen Bernhard und der große Fluss

Bäuerchen Bernhard verdient seinen Lebensunterhalt damit landwirtschaftliche Erzeugnisse in der Stadt zu verkaufen. Zwischen seinem Hof und dieser Stadt fließt jedoch ein breiter Fluss. Um ihn zu überqueren hat er dort ein kleines Boot geparkt. In diesem Boot ist gerade genug Platz für ihn selbst und noch für ein anderes Ding.

Leider sind nicht alle seiner Erzeugnisse friedlich, manche Fressen sich sogar gegenseitig. Da Bernhard flink und tapfer ist kann er das verhindern, solange er direkt dabei ist. Wenn er sich allerdings mit einem Erzeugnis ins Boot setzt kann er nicht mehr auf die anderen aufpassen.

Er muss sich also genau überlegen in welcher Reihenfolge er die Tiere über den Fluss bringt. Gestern hatte er es noch geschafft einen Wolf, eine Ziege und einen Kohlkopf heil in die Stadt zu bringen. Doch heute hat er noch ein Schaf dabei.

Auch nach längerem Nachdenken fällt ihm keine Möglichkeit ein die Vier heil über den Fluss zu bekommen. Er müsste also seine beiden Söhne um Hilfe bitten. Aber er ist sich nicht ganz sicher ob es wirklich keine Möglichkeit gibt. Da wäre ein Computerprogramm gut, das das entscheiden kann.

Es geht also darum dieses Programm für Bernhard zu schreiben. Dabei muss das folgende beachtet werden:

Um das Programm universell verwendbar zu machen werden die Arten der landwirtschaftlichen Erzeugnisse durchnummeriert. Die Nummerierung beginnt bei Null.

Eingabe (fluss.in)

Ausgabe (fluss.out)

Es wird zeilenweise nacheinander ausgegeben was Bernhard über den Fluss transportieren muss. L wenn das Boot leer bleibt und ansonsten eine Zahl für das entsprechende Erzeugnis. Nachdem alle Erzeugnisse auf der anderen Seite sind, wird ein F in der letzten Zeile ausgegeben. Wenn es nicht möglich ist die Tiere sicher ans andere Ufer zu bringen, also die Hilfe der Söhne nötig ist, wird nur dieses F ausgegeben.

Nicht vergessen: Die Ausgabe muss mit einem Zeilenumbruch ("\n" in C/C++) abgeschlossen werden.

Beispiel

Dies ist das von Bernhard schon gelöste Probelm (0=Kohl, 1=Ziege, 2=Wolf)

Eingabedatei (fluss.in)

3
0
1
0
1
1

Ausgabedatei (fluss.out)

1
L
0
1
2
L
1
F

Limits

Zeitlimit: 1 Sekunde
Speicherlimit: 32 MB

Bäuerchen Bernhard und der große Fluss

Musterlösung

Diese Aufgabe Informatik kann als graphentheoretisches Problem betrachtet werden. Dabei ist jedes Erzeugnis ein Knoten. Wenn zwei sich fressen werden sie durch eine Kante verbunden. Die Richtung des gefressen Werdens ist für das Problem nicht wichtig. Es wird also ein ungerichteter Graph verwendet. Damit das Problem lösbar ist muss es möglich sein durch Entfernen eines Knotens alle Kanten zu beseitigen. Es gibt also einen Knoten der von allen Kanten berührt wird. Wenn dieser Knoten von 3 oder mehr Kanten berührt wird, ist das Problem nicht lösbar. Der Graph hat also höchstens 2 Kanten. Daher wird in dieser Musterlösung auf eine echte Graphenimplementation verzichtet. Es kommen also die folgenden 3 Graphenstrukturen in Frage:

Der letzte dieser Fälle ist der komplizierteste. Der Knoten, der von beiden Kanten berührt wird, wird dabei mittlerer Knoten genannt. Dieser muss zuerst über den Fluss gebracht werden. Dadurch ist sichergestellt, dass niemand gefressen wird. Jetzt können alle unbeteiligten Erzeugnisse auf die richtige Seite gebracht werden.

Dannach wird eines der übrigen Erzeugnisse auf die richtige Seite gebracht. Dort ist es mit dem Mittleren zusammen. Falls der Graph 2 Kanten hat muss das Mittlere also wieder auf die ursprüngliche Seite gebracht werden. Von dort kann dann das letzte Erzeugniss auf die Seite der Stadt gebracht werden. Da das Mittlere nicht dort ist, wird trotzdem niemand gefressen. Am Ende muss dann noch das Mittlere Erzeugnis auf die richtige Seite gebracht werden.

Die grundsätzliche Strategie ist also immer:

Falls der Graph kleiner ist, also nur eine Kante ist, kann das Vorgehen entsprechend vereinfacht werden.

#include <iostream>
#include <fstream>

using namespace std;

inline void addedge(int, int);

inline void failed();
inline void result();
inline bool isSpecial(int);


int animalnumber; // Die Anzahl der vorhandenen Erzeugnisse
// edge1 und edge2 sind die beiden Kanten. Wenn eine Kante

// nicht existiert werden ihre Knoten auf -1 gesetzt

int edge1a(-1), edge1b(-1), edge2a(-1), edge2b(-1);
// Die maximal 3 Knoten, die von den beiden Kanten berührt werden.

int aMiddle(-1), aLeft(-1), aRight(-1);

int main() 
{
// Eingabe einlesen und in den Graphen übertragen:

	ifstream infile("fluss.in");
	infile >> animalnumber;
	for(int i=0; i<animalnumber; i++) {
		int eatnum;
		infile >> eatnum;
		if(eatnum>2)failed();
		for(int food=0; food<eatnum; food++) {
			int foodnum;
			infile>>foodnum;
			addedge(i, foodnum);
		}
	}
	

// einfachster Fall, kein Erzeugnis frisst etwas:
	if(edge1a==-1 && edge2a==-1) 
	{
		result();
	}	

// Fressgraph hat nur eine Kante:
	if(edge2a==-1) 
	{
		aMiddle=edge1a;
		aLeft=edge1b;
		result();
	}
// Fressgraph ist nicht zusammenhängend:

	if((edge1a!=edge2a) && (edge1a!=edge2b) 
	&& (edge1b!=edge2a) && (edge1b!=edge2b)) failed();

// Restliche Fälle: Fressgraph hat die Form left-middle-right

	if(edge1a==edge2a) 
	{
		aMiddle=edge1a;
		aLeft=edge1b;
		aRight=edge2b;
	}
	if(edge1a==edge2b) 
	{
		aMiddle=edge1a;
		aLeft=edge1b;
		aRight=edge2a;
	}
	if(edge1b==edge2a) 
	{
		aMiddle=edge1b;
		aLeft=edge1a;
		aRight=edge2b;
	}
	if(edge1b==edge2b) 
	{
		aMiddle=edge1b;
		aLeft=edge1a;
		aRight=edge2a;
	}
	result();
}

/*
fügt die Kante (a,b) zum Graphen hinzu
*/
inline void addedge(int a, int b) 
{
	if(edge1a==-1) 
	{
		edge1a=a;
		edge1b=b; 
		return;
	}
	else if((edge1a==a && edge1b==b) || (edge1a==b && edge1b==a)) 
	{
		return;
	}
	else if(edge2a==-1) 
	{
		edge2a=a;
		edge2b=b;
		return;	
	}
	else if((edge2a==a && edge2b==b) || (edge2a==b && edge2b==a)) 
	{
		return;
	}

// Bei mehr als 2 Kanten ist das Problem nicht lösbar:	

	failed(); 
}

/*
Ausgabe, dass das Problem nicht lösbar ist 
und Programm beenden
*/
inline void failed() 
{
	ofstream outfile("fluss.out");
	outfile<<"F"<<endl;
	outfile.close();
	exit(0);
}

/*
Hier wird eine existierende Lösung ausgegeben
*/

inline void result()
{
// zuerst den mittleren rüber damit sich niemand auffrisst:

	ofstream outfile("fluss.out");
	if(aMiddle!=-1) 
	{
		outfile<<aMiddle<<endl;
		outfile<<"L"<<endl;
	}	
// dann alle unbeteiligten Erzeugnisse rüber:

	
	for(int i=0; i<animalnumber; i++) 
	{
		if(!isSpecial(i)) 
		{	
			outfile<<i<<endl;
			outfile<<"L"<<endl;
		}
	}
//(Hier immer auf der Seite des Hofs)

// Jetzt die Problematischen
	if(aMiddle!=-1) {
		outfile<<aLeft<<endl;
		if(aRight!=-1) 
		{
			outfile<<aMiddle<<endl;
			outfile<<aRight<<endl;
			outfile<<"L"<<endl;
			outfile<<aMiddle<<endl;	
		}
	}

// Falls der Fressgraph keine Kanten hat, muss man noch 

// auf die richtige Seite fahren:
	else {
		outfile<<"L"<<endl;
	}
	outfile<<"F"<<endl;
	outfile.close();
	exit(0);		
}


inline bool isSpecial(int i) {
	return (i==aMiddle || i==aLeft || i==aRight);
}

Primzahlen

In diesem Problem geht es um die Berechnung von Primzahlen. Zur Erinnerung: eine Primzahl ist eine Zahl, die nur durch 1 und sich selbst teilbar ist, und deren Teilermenge genau zwei Elemente hat (d.h. 1 ist keine Primzahl). Du bekommst zwei Zahlen A und B (A ≤ B) gegeben und sollst alle Primzahlen ausgeben, die zwischen A und B liegen.

Eingabeformat (prim.in)

Zeile 1: Die zwei Zahlen A und B (0 ≤ A ≤ B ≤ 2000000000, B - A ≤ 1000000), durch ein Leerzeichen getrennt.

Ausgabeformat (prim.out)

Zeile i: Die i-te Primzahl zwischen A und B.

Beispiel

Eingabe (prim.in)

1 11

Ausgabe (prim.out)

2
3
5
7

Kommentar

Es gibt genau 4 primzahlen zwischen 1 und 11: 2, 3, 5 und 7.

Limits

Zeitlimit: 1 Sekunde
Speicherlimit: 32 MB

Primzahlen

Musterlösung

Naheliegende Lösung

#include <cstdio>

using namespace std;

// Ueberpruefung, ob p eine Primzahl ist
// Annahme: p ist nicht durch Zwei teilbar!
int is_prime (int p)
{
    // p ist hier auf keinen Fall mehr durch Zwei teilbar, deshalb
    // muessen nur noch ungerade Teiler ausprobiert werden.
    for (int i = 3; i * i <= p; i += 2)
        // p ist genau dann durch i teilbar,
        // wenn der rest der Division p / i = 0
        if (p % i == 0) return 0;
    // p war durch kein i teilbar, also ist p eine Primzahl
    return 1;
}

int main ()
{
    FILE *fin = fopen ("prim.in", "r"), *fout = fopen ("prim.out", "w");
    int A, B;
    fscanf (fin, "%d %d", &A, &B);
    // 2 ist ein Sonderfall (und die kleinste moegliche Primzahl):
    if (A < 2) fprintf (fout, "2\n");
    // p ist die naechste ungerade Zahl nach A und wird um zwei
    // erhoeht, solange p < B, deshalb ist p immer ungerade, so
    // wie von der Funktion is_prime gefordert.
    for (int p = ((A+1)/2)*2 + 1; p < B; p+=2)
        // falls p eine Primzahl ist, wird p ausgegeben
        if (is_prime (p)) fprintf (fout, "%d\n", p);
    fclose (fin); fclose (fout);
    return 0;
}

Es werden einfach alle Zahlen zwischen A und B auf ihre Primzahleigenschaft getestet und gegebenenfalls ausgegeben. Dieses Programm enthält schon einige Optimierungen:

Beim Primzahltest muss eigentlich nur auf Teilbarkeit durch Primzahlen getestet werden. So könnte eine weitere Optimierung aussehen.

Die Laufzeit des Algorithmus ist nicht leicht zu zeigen: die Funktion is_prime (p) hat im Mittel (für ausreichend großes N) eine Laufzeit, die nicht schlechter ist als log (p). Da p maximal B ist, kann die Laufzeit mit O (log (B)) angegeben werden. Diese Schleife wird etwa N/2 mal aufgerufen, wenn N den Abstand zwischen A und B bezeichnet, daher kann die Gesamtlaufzeit mit O(N * log (B)) angegeben werden.

Das Sieb des Eratosthenes

#include <cstdio>
#include <memory.h>

using namespace std;

// prime_array [p] ist 1, wenn die Zahl A + 1 + p
// keine Primzahl ist!
int not_prime [1000001];

int main ()
{
    FILE *fin = fopen ("prim.in", "r"), *fout = fopen ("prim.out", "w");
    int A, B;
    fscanf (fin, "%d %d", &A, &B);
    memset (not_prime, 0, sizeof (not_prime));
    // alle Zahlen, die durch a teilbar sind als "nicht prim" markieren.
    for (int a = 2; a*a < B; a++) {
        int p_start = (A / a + 1) * a;
        if (p_start == a) p_start += a;

        // p ist zunaechst die Zahl nach A, die durch a teilbar (und nicht a selbst)
        // ist und wird dann so lange um a erhoeht, bis p >= B.
        for (int p = p_start; p < B; p += a)
            not_prime [p-A-1] = 1;
    }
    // alle Zahlen, die jetzt noch nicht "nicht prim" sind,
    // werden ausgegeben
    for (int p = A+1; p < B; p++)
        if (!not_prime [p - A - 1]) fprintf (fout, "%d\n", p);
    fclose (fin); fclose (fout);
}

Das Sieb des Eratosthenes ist ein weit bekannter Algorithmus zum Suchen von Primzahlen. Es gibt ein Feld, in dem jedes Element einer Zahl zwischen A und B zugeordnet ist, und auf 1 gesetzt wird, sobald festgestellt wird, dass diese Zahl keine Primzahl ist. Nun werden zunüchst alle geraden Zahlen auf "nicht prim" gesetzt, anschließend alle durch drei teilbaren Zahlen, usw. Auch hier ist die Laufzeit nicht einfach zu zeigen, aber die äußere Schleife wird nur Wurzel (B) mal durchlaufen und die innere Schleife ist ähnlich wie die vorhergehende is_prime Funktion aufgebaut. Die tatsächliche Laufzeit dieses Algorithmus beträgt O (N * log (Wurzel (B))). Für große N und B ist er noch etwas zu langsam.

Dieses Verfahren ist auch sehr schön in der Wikipedia erklärt

Es gibt noch eine entscheidende Verbesserung, die auf obigen Algorithmus angewandt werden kann: die innere Schleife muss nicht für alle Zahlen unter Wurzel(B) ausgeführt werden, sondern lediglich für die Primzahlen. Um dies Sicherzustellen kann man alle Primzahlen im Vorhinein berechnen und nur noch diese verwenden:

#include <cstdio>
#include <list>
#include <memory.h>

using namespace std;

// prime_array [p] ist 1, wenn die Zahl A + 1 + p
// keine Primzahl ist!
int prime_array [1000001], primes [40000], pcount = 0;

void check_prime (int p)
{
    // auf Teilbarkeit durch andere Primzahlen testen
    for (int cp = 0; cp < pcount && primes [cp] * primes [cp] <= p; cp++)
        if (p % primes [cp] == 0) return;
    // diese Zahl ist eine Primzahl
    primes[pcount++] = p;
}

int main ()
{
    FILE *fin = fopen ("prim.in", "r"), *fout = fopen ("prim.out", "w");
    int A, B;
    fscanf (fin, "%d %d", &A, &B);
    memset (prime_array, 0, sizeof (prime_array));
    primes [pcount++] = 2;
    for (int p = 3; p * p < B; p+=2) check_prime (p);
    // alle Zahlen, die durch a teilbar sind als "nicht prim" markieren.
    for (int ia = 0; primes [ia]*primes [ia] < B && ia < pcount; ia++) {
        int a = primes [ia];
        int p_start = (A / a + 1) * a;
        if (p_start == a) p_start += a;

        // p ist zunaechst die Zahl nach A, die durch a teilbar (und nicht a selbst)
        // ist und wird dann so lange um a erhoeht, bis p >= B.
        for (int p = p_start; p < B; p += a)
            prime_array [p-A-1] = 1;
    }
    // alle Zahlen, die jetzt noch nicht "nicht prim" sind,
    // werden ausgegeben
    for (int p = A+1; p < B; p++)
        if (!prime_array [p - A - 1]) fprintf (fout, "%d\n", p);
    fclose (fin); fclose (fout);
}

Die Laufzeit für diesen Algorithmus liegt grob bei O(Wurzel (B) * log (Wurzel (B)) + N * log (Wurzel (B) / ln (Wurzel (B)))). Er ist für alle Eingabegrößen schnell genug.

Elmos Reise

Elmo plant die nächsten Sommerferien, die er in den USA verbringen möchte. Es gibt eine ganze Menge großer Städte, die er sich gerne ansehen würde. Auf jeden Fall möchte Elmo aber möglichst wenig Zeit im Flugzeug und Zug verbringen. Hilf Elmo seine Route zu planen, indem du die bestehenden Zug- und Flugverbindungen zwischen den Städten, die Elmo besuchen möchte, aus der Datei reise.in einliest und dann die Reihenfolge ausgibst, in der Elmo die Städte besuchen soll. Elmo guckt sich keine Stadt zweimal an, aber es kann sein, dass er auf seiner Reise von einer Stadt zur anderen in einer Stadt vorbeikommt, die er bereits besucht hat. Da sein Flieger aus Süd-Berlin in New York landet und auf dem Rückweg wieder von dort startet, muss er seine Reise dort beginnen und auch wieder beenden.

Es gibt auf jeden Fall eine direkte oder indirekte Verbindung zwischen zwei beliebigen Städten. Auf jeden Fall gibt es nur maximal eine direkte Verbindung zwischen zwei Städten. Jede Verbindung kann in beide Richtungen genutzt werden.

Eingabe (reise.in)

Zeile 1: Zwei Zahlen N und M. N (2≤N≤9) ist die Anzahl der Städte, die Elmo besuchen möchte. M (1≤M≤100) ist die Anzahl der Verbindungen, die es zwischen den Städten gibt.
Zeile 2..N+1: Die Namen der Städte, die Elmo besuchen möchte. Die Stadtnamen haben nur Groß- und Kleinbuchstaben und enthalten keine Leerzeichen, die Groß- und Kleinschreibung ist zu beachten. Zeile 2 ist auf jeden Fall "NewYork". Dort soll Elmos Reise starten und enden. Der Name keiner Stadt enthält mehr als 30 Zeichen.
Zeile N+2..N+2+M: Die Namen zweier Städte A und B (die Elmo auf jeden Fall besuchen möchte) und die Dauer D der Verbindung zwischen beiden Städten in Minuten. D ist ein Integer und liegt zwischen 0 und 100000.

Ausgabe (reise.out)

Zeile 1..N+1: Die Städte in der Reihenfolge, in der Elmo sie besuchen soll. Wenn es mehrere Möglichkeiten gibt, gib irgendeine davon aus. Die erste und letzte Zeile müssen "NewYork" enthalten.

Beispiel

Eingabe (reise.in)

5 6
NewYork
Philadelphia
LosAngeles
WashingtonDC
Chicago
NewYork Philadelphia 120
NewYork LosAngeles 174
LosAngeles Chicago 194
Chicago WashingtonDC 119
Chicago NewYork 145
WashingtonDC Philadelphia 92

Ausgabe (reise.out)

NewYork
Philadelphia
WashingtonDC
Chicago
LosAngeles
NewYork

Details

Von NewYork nach Philadelphia sind es 120 Minuten, danach fliegt Elmo von Philadelphia 92 Minuten nach WashingtonDC, um von dort in 119 Minuten nach Chicago weiterzureisen. Nach LosAngeles sind es dann noch 194 Minuten. Schließlich muss er noch nach NewYork zurück, was 174 Minuten dauert. Zusammen dauert seine Reise also 699 Minuten. Es gibt keine kürzere Verbindung, um alle Städte zu besuchen.

Limits

Zeitlimit: 1 Sekunde
Speicherlimit: 32 MB

Elmos Reise - Musterlösung

Lösungsidee

An den Beschränkungen Eingabegrößen kann man leicht erkennen, dass es für dieses Problem wohl (derzeit noch) keine effiziente Lösung gibt. Es müssen also alle Möglichkeiten, die Reise zu gestalten, nacheinander durchprobiert werden. Tatsächlich ist diese Aufgabe genau das Problem des Hamilton-Cycles, ein Standardproblem der Informatik. Das Problem ist eigentlich für Graphen definiert: Ist ein gegebener Weg, der jeden Knoten eines Graphen genau einmal besucht, optimal, d.h. ist die Summe seiner Kantengewichte minimal? Natürlich können und sollten die Städte und ihre Verbindungen ebenfalls als Graph interpretiert werden.

Die Aufgabe erfordet allerdings noch einen weiteren Algorithmus, denn es dürfen ja auch indirekte Verbindungen zwischen zwei Städten genutzt werden. Es kann also sein, dass zwei Städte, die in der Ausgabe direkt aufeinanderfolgen, gar nicht direkt miteinander verbunden sind. Deswegen muss auf jeden Fall der Abstand zwischen zwei beliebigen Städten bekannt sein. Es gibt mehrere Algorithmen, die den Abstand zwischen allen Knoten eines Graphen berechnen (All-Pairs Shortest-Paths), am gelaeufigsten und am einfachsten zu implementieren ist jedoch der Floyd-Warshall Algorithmus, der in O (N^3) läuft (wobei N die Anzahl der Knoten ist). Für N ≤ 9 auf jeden Fall ausreichend. (Vergleiche: Tomas H. Cormen et al: Introduction to Algorithms, p. 629)

Es gibt noch ein weiteres Problem, das angsprochen werden sollte: die Namen der Städte müssen auf irgendwelche IDs gemappt werden, damit das Problem vernünftig bearbeitet werden kann. Eine Möglichkeit dies zu tun ist es, alle Namen in einer Liste zu speichern und dann als ID die Position einer Stadt in der Liste zu verwenden. Für C++ bietet die STL allerdings eine wesentlich elegantere und effizientere Möglichkeit: die map Klasse. Die Implementation kann z.B. wie weiter unten aufgelistet geschehen.

Der Algorithmus geht wie folgt vor: Zunächst werden alle kürzesten Pfade ermittelt und in dem Array dist abgespeichert. dist [a][b] enthält dann die Länge der kürzesten Verbindung von a nach b. Anschließend werden mit der rekursiven Funktion find_route alle möglichen Abfolgen der Städte durchprobiert. Wenn ein neuer kürzester Weg gefunden wurde, wird dieser abgespeichert. Um den Suchbaum ein bisschen zu verkleinern, wird abgebrochen, sobald der aktuelle Weg länger als der kürzeste ist.

Laufzeit

Die Laufzeitanalyse ist relativ simpel. Da es sich um ein NP-vollständiges Problem handelt, kann die Laufzeit des All-Pairs Shortest-Paths Algorithmus vernachläsigt werden und die Laufzeit mit O (N!) angegeben werden.

Der Quelltext

#include <cstdio>
#include <map>
#include <string>
#include <list>

using namespace std;

FILE *fin = fopen ("reise.in", "r"),
     *fout = fopen ("reise.out", "w");

#define INFDIST 1000000

map <string, int> IDs;
map <int, string> Cities;


int dist [10][10],          // Distanz zwischen zwei Staedten A und B
    visited [10],           // wurde eine Stadt schon besucht
    min_dist = INFDIST,     // Laenge der kuerzesten Reise
    N, M;

list <int> cur_route,       // aktuell betrachtete Reise
           best_route;      // beste Reise

void find_route (int city, int cur_dist)
{
    int found = 0;

    // Wir koennen abbrechen, wenn die bestehende Route
    // laenger als die beste bisher gefundene ist.
    if (cur_dist > min_dist) visited [city] = 0;

    visited [city] = 1;

    for (int n = 0; n < N; n++) {
        if (!visited [n]) {
            found = 1;
            cur_route.push_back (n);
            find_route (n, cur_dist + dist [city][n]);
            cur_route.pop_back ();
        }
    }

    // Keine Staedte mehr zu besuchen?
    if (found == 0) {
        cur_dist += dist [city][IDs ["NewYork"]];
        // gibt es eine neue beste route
        if (cur_dist < min_dist) {
            cur_route.push_back (IDs ["NewYork"]);
            best_route = cur_route;
            min_dist = cur_dist;
            cur_route.pop_back ();
        }
    }

    visited [city] = 0;
}

int main ()
{
    fscanf (fin, "%d %d", &N, &M);

    for (int n = 0; n < N; n++) {
        char city [32];
        fscanf (fin, "%s", &city);
        int curID = (int)IDs.size ();
        IDs [city] = curID;
        Cities [IDs [city]] = city;
    }

    // zunaechst alle Entfernungen auf
    // das Maximum setzen und jede Stadt hat
    // zu sich selbst die Entfernung 0
    for (int a = 0; a < N; a++)
        for (int b = 0; b < N; b++)
            dist [a][b] = (a == b)?0:INFDIST;

    // direkte Verbindungen einlesen
    for (int m = 0; m < M; m++) {
        char A [32], B [32];
        int D;
        fscanf (fin, "%s %s %d", &A, &B, &D);
        dist [IDs [A]][IDs [B]] = dist [IDs [B]][IDs [A]] = D;
    }

    // All-Pairs Shortest-Paths Algorithmus
    // um indirekte Entfernungen zu ermitteln
    for (int c = 0; c < N; c++) {
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < N; b++) {
                // ist es kürzer von a nach c zu reisen und dann
                // von c nach b, als von a nach b direkt?
                if (dist [a][c] + dist [c][b] < dist [a][b])
                    dist [a][b] = dist [a][c] + dist [c][b];
            }
        }
    }

    // alle visited zustände auf 0 setzen
    for (int n = 0; n < N; n++)
        visited [n] = 0;

    // in NewYork geht es los
    cur_route.push_back (IDs ["NewYork"]);
    find_route (0, 0);

    // beste gefundene Reise ausgeben
    for (list <int>::iterator it = best_route.begin (); it != best_route.end (); it++)
        fprintf (fout, "%s\n", Cities [*it].c_str ());

    return 0;
}