ACM International Collegiate Programming Contest
Japan Domestic, 1999-11-05
Problem E
A Long Ride on a Railway
Travelling by train is fun and exciting. But more than that indeed. Young
challenging boys often tried to purchase the longest single tickets and to
single ride the longest routes of various railway systems. Route planning was
like solving puzzles. However, once assisted by computers, and supplied with
machine readable databases, it is not any more than elaborating or hacking
on the depth-first search algorithms.
Map of a railway system is essentially displayed in the form of a graph. (See
the Figures below.) The vertices (i.e. points) correspond to stations and the
edges (i.e. lines) correspond to direct routes between stations. The station
names (denoted by positive integers and shown in the upright letters in the
Figures) and direct route distances (shown in the slanted letters) are also
given.
The problem is to find the length of the longest path and to form the
corresponding list of stations on the path for each system. The longest of
such paths is one that starts from one station and, after travelling many
direct routes as far as possible without passing any direct route more than
once, arrives at a station which may be the starting station or different one
and is longer than any other sequence of direct routes. Any station may be
visited any number of times in travelling the path if you like.
Input
The graph of a system is defined by a set of lines of integers of the
form:
| ns | nl |
| s1,1 |
s1,2 |
d1 |
| s2,1 |
s2,2 |
d2 |
| ... |
| snl,1 |
snl,2 |
dnl |
Here 1 <= ns <= 10 is the number of stations (so, station names are 1, 2,
..., ns), and 1 <= nl <= 20 is the number of direct routes in this
graph.
si,1 and si,2
(i = 1, 2, ..., nl) are station names at the both ends of the
i-th direct route. di >= 1 (i = 1, 2, ...,
nl) is the direct route distance between two different stations
si,1 and si,2.
It is also known that there is at most one direct route between any pair of
stations, and all direct routes can be travelled in either directions. Each
station has at most four direct routes leaving from it.
The integers in an input line are separated by at least one white space (i.e. a
space character (ASCII code 32) or a tab character (ASCII code 9)), and possibly
preceded and followed by a number of white spaces.
The whole input of this problem consists of a few number of sets each of which
represents one graph (i.e. system) and the input terminates with two integer
0's in the line of next ns and nl.
Output
Paths may be travelled from either end; loops can be traced clockwise or
anticlockwise. So, the station lists for the longest path for Figure A are
multiple like (in lexicographic order):
2 3 4 5
5 4 3 2
For Figure B, the station lists for the longest path are also multiple like
(again in lexicographic order):
6 2 5 9 6 7
6 9 5 2 6 7
7 6 2 5 9 6
7 6 9 5 2 6
Yet there may be the case where the longest paths are not unique. (That is,
multiple independent paths happen to have the same longest distance.) To make
the answer canonical, it is required to answer the lexicographically least
station list of the path(s) for each set. Thus for Figure A,
2 3 4 5
and for Figure B,
6 2 5 9 6 7
must be reported as the answer station list in a single line. The integers in a
station list must be separated by at least one white space. The line of
station list must be preceded by a separate line that gives the length of the
corresponding path. Every output line may start with white spaces. (See output
sample.)
Sample Input
6 5
1 3 10
2 3 12
3 4 2
4 5 13
4 6 11
10 10
1 2 11
2 3 25
2 5 81
2 6 82
4 5 58
5 9 68
6 7 80
6 9 67
8 9 44
9 10 21
0 0
Warning: The station names are given in the lexicographic order here. The
contestants should not depend on the order.
Output for the Sample Input
27
2 3 4 5
378
6 2 5 9 6 7
First Input Data
Your first input data is here.
The ACM ICPC