236. Greedy Path
time limit per test: 0.25
sec.
memory limit per test: 4096
KB
input: standard
output: standard
There are N towns and M routes between them. Recently, some new travel agency was founded for servicing tourists in these cities. We know cost which tourist has to pay, when traveling from town i to town j which equals to Cij and time needed for this travel  Tij. There are many tourists who want to use this agency because of very low rates for travels, but agency still has only one bus. Head of agency decided to organize one big travel route to gain maximal possible amount of money. Scientists of the company offer to find such a cyclic path G, when greedy function f(G) will be maximum. Greedy function for some path is calculated as total cost of the path (sum of Cij for all (i,j)  routes used in path) divided by total time of path (similar to Cij). But nobody can find this path, and Head of the company asks you to help him in solving this problem.
Input
There are two integers N and M on the first line of input file (3<=N<=50). Next M lines contain routes information, one route per line. Every route description has format A, B, Cab, Tab, where A is starting town for route, B  ending town for route, Cab  cost of route and Tab  time of route (1<=Cab<=100; 1<=Tab<=100; A<>B). Note that order of towns in route is significant  route (i,j) is not equal to route (j,i). There is at most one route (in one direction) between any two towns.
Output
You must output requested path G in the following format. On the first line of output file you must output K  number of towns in the path (2<=K<=50), on the second line  numbers of these towns in order of passing them. If there are many such ways  output any one of them, if there are no such ways  output "0" (without quotes).
Sample test(s)
Input
4 5
1 2 5 1
2 3 3 5
3 4 1 1
4 1 5 2
2 4 1 10
Output
4
1 2 3 4
Author:  Sergey Simonchik

Resource:  

Date:  December, 2003

Server time: 20160927 14:21:14  Online Contester Team © 2002  2016. All rights reserved. 

