## 205 - Getting There

Moderator: Board moderators

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

### 205 - Getting There

My program solves this problem for the sample input/output exactly, and the problem said that the sample handles all cases. Maybe it doesn't?

Can someone post some sample data that this doesn't work with? I know a lot of people haven't solved this, but it looks like I have almost.

Code: Select all

``````/*   @JUDGE_ID:   xxxxxx   205   C++ */
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

struct Flight
{
string toName;
int to;
int departure;
int arrival;
double cost;
};

struct City
{
string name;
vector<Flight> flights;
City()
{
}
City(string name) : name(name)
{
}
};

string itoa(int x)
{
string s;
if (x == 0)
return "0";
int y = 1;
while (x / y)
y *= 10;
while (y /= 10)
s.push_back('0' +  (x / y) % 10);
return s;
}

string translateTime(int t)
{
string s;
int d = t / 1440;
int h = t / 60 % 24;
int m = t % 60;
char buff[80];
if (d)
{
s += itoa(d) + " day";
if (d > 1)
s.push_back('s');
s.push_back(' ');
}
s += itoa(h) + ":";
s.push_back('0' + m/10);
s.push_back('0' + m%10);
return s;
}

string translateTOD(int t)
{
string s = translateTime(t % 720);
s.push_back((t%1440) >= 720 ? 'P' : 'A');
return s;
}

{
while (s.size() < width)
s.push_back(' ');
return s;
}

{
string space;
while (s.size() < width)
{
space.push_back(' ');
width--;
}
return space + s;
}

void normalize(string &s)
{
transform(s.begin(), s.end(), s.begin(), tolower);
s[0] = toupper(s[0]);
}

int timeAfter(int t, int d)
{
while (d <= t)
d += 1440;
return d;
}

string translateCost(double d)
{
string s = "\$";
s += itoa(int(floor(d)));
int x = int(floor(d * 100));
s.push_back('.');
s.push_back('0' + (x / 10) % 10);
s.push_back('0' + (x % 10));
return s;
}

struct Graph
{
vector<City> cities;
map<string, int> numbers;

void resolveFlights()
{
for (int i = 0; i < cities.size(); i++)
numbers[cities[i].name] = i;

for (int i = 0; i < cities.size(); i++)
for (int j = 0; j < cities[i].flights.size(); j++)
cities[i].flights[j].to =
numbers[cities[i].flights[j].toName];
}

void bestRoute(string fromName, string toName, string opt)
{
normalize(toName); normalize(fromName); normalize(opt);
if (fromName == toName)
{
cout << "You are already in " << toName << "." << endl;
return;
}
bool byCost = opt == "Cost";
int from = numbers[fromName];
int to = numbers[toName];
int cityNum = from;
double cost[20];
int route[20];
int flight[20];
int time[20];
bool visited[20];
for (int i = 0; i < cities.size(); i++)
{
cost[i] = 1000000;
time[i] = 1000000;
visited[i] = false;
route[i] = -1;
flight[i] = -1;
}
time[from] = 0;
cost[from] = 0;
route[from] = -1;
flight[from] = -1;
while (cityNum != to)
{
City &city = cities[cityNum];
visited[cityNum] = true;
int t = time[cityNum];
double c = cost[cityNum];
for (int i = 0; i < city.flights.size(); i++)
{
int toCity = city.flights[i].to;
int dep = timeAfter(time[cityNum],
city.flights[i].departure);
int arr = dep - city.flights[i].departure +
city.flights[i].arrival;
double co = c + city.flights[i].cost;
bool fly;
fly = byCost ?
(cost[toCity] > co ||
(cost[toCity]==co && time[toCity]>arr))
:
(time[toCity]>arr ||
(time[toCity]==arr&&cost[toCity]>co));

if (fly)
{
cost[toCity] = co;
time[toCity] = arr;
route[toCity] = cityNum;
flight[toCity] = i;
}
}
int best = 0;
while (best < cities.size() && visited[best])
best++;
for (int i = best+1; i < cities.size(); i++)
if (!visited[i])
{
if (byCost)
{
if (cost[i] < cost[best])
best = i;
}
else
if (time[i] < time[best])
best = i;
}
cityNum = best;
}
vector<int> fullRoute;
cityNum = to;
while (cityNum >= 0 && cityNum != from)
{
fullRoute.push_back(cityNum);
cityNum = route[cityNum];
}
if (cityNum < 0)
{
cout << "There is no route from " << fromName <<
" to " << toName << "." << endl;
return;
}

cout << "From: " << rightPad(fromName, 20) <<
" To: " << rightPad(toName, 20)<<
" Optimize: " << opt << endl <<
"================================="
"=================================" << endl <<
"From                To           "
"          Leave   Arrive     Cost" << endl <<
"================================="
"=================================" << endl;

int f = from;
int curTime = 0;
int startTime = cities[f].flights[flight[fullRoute.back()]].
departure;
double totalCost = 0;
while (fullRoute.size())
{
int t = fullRoute.back();
fullRoute.pop_back();
Flight &fl = cities[f].flights[flight[t]];
endl;
totalCost += fl.cost;
curTime = timeAfter(curTime-1, fl.departure);
curTime = timeAfter(curTime, fl.arrival);
f = t;
}
cout << "                                 "
"          -----------------------" << endl <<
}
};

{
int h;
in >> h;
in.ignore(1);
int m;
in >> m;
if (in.get() == 'P')
h += 12;
return h * 60 + m;
}

istream &operator>>(istream &in, Flight &f)
{
in >> f.toName;
normalize(f.toName);
return in >> f.cost;
}

istream &operator>>(istream &in, Graph &g)
{
g.cities.resize(0);
map<string, City> cities;
string from;
while (in >> from && from != "#")
{
normalize(from);
City &city = cities[from];
city.name = from;
Flight f;
in >> f;
cities[f.toName].name = f.toName;
city.flights.push_back(f);
}
map<string, City>::iterator city;
for (city = cities.begin(); city != cities.end(); city++)
g.cities.push_back(city->second);
g.resolveFlights();
return in;
}

int main(int argc, char *argv[])
{
string travel;
bool first = true;
while (cin >> travel)
{
int id;
cin >> id;
if (!first)
cout << endl << endl;
first = false;
cout << "Requests and optimal routes for travel " << id <<
endl <<
"------------------------------------------" << endl <<
endl;
Graph g;
cin >> g;
bool first2 = true;
string s;
while (cin >> s && cin && s != "#")
{
string d, opt;
cin >> d >> opt;

if (!first2)
cout << endl;
first2 = false;

g.bestRoute(s, d, opt);
}
}
return 0;
}
``````

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
I didn't go through your code.. but here's some common tripups that I saw.

1) Time for each FLIGHT <24 hours. But time for each TRIP can take as long as possible.

2) If there is multiple optimals, then you need to optimal the other criteria as well.

3) You cannot use DP for this question.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 205 - Getting There

If I remember correctly, the AM/PM clock has twelve hours, from 1 to 12 inclusive, and there is no hour zero. But according to the problem description, in this problem there is, which automatically excludes the hour 12. But to my astonishment, the input file contains both 0 and 12 in the hour! But how to interpret this? Is 12:30A the same as 0:30A or is it 0:30P? And what about 12:30P, is it 0:30A the next day?

Farid, you realy messed this one up...

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I think the input file doesn't contain an hour 12. I just send my program again to the judge with an assert(h<12); and it got Accepted.
Check your parsing routine, for example the hour 5 may be given as 05 or as 5 (with one space before the 5).
By the way, as far as I know Farid didn't change anything on the problem description, so don't blame him.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I feel terribly ashamed, there is no hour 12 in the input. I had my assert in the wrong place
Please ignore my posting. Sorry Farid.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
This problem can be solved by shortest path algorithms.

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm
sclo wrote:This problem can be solved by shortest path algorithms.
As a matter of fact, that's exactly the algorith I used.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
Salamo Aleko
Can any one give me some test cases
Sleep enough after death, it is the time to work.

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
So, to convert from 12-hour-clock to 24-hour-clock is just:

twentyFour = HH*60 + MM + (X=='A' ? 0 : 12*60);

and to convert back from 24-hour-clock to 12-hour-clock is just:

HH = (twentyFour/60) % 12
MM = twentyFour%60
X = (twentyFour/60)<12? 'A' : 'P'

is that correct?

I also have question regarding no output > 10 days or > \$1000 :

I used A* search to solve this problem. According to A* algorithm, it will stop immediately when it found a solution and it is guaranteed to be optimal.

When I put assert(currentTime < 10 days && currentCost < \$1000) and submit, it gives runtime error, meaning that the A* still doesn't found a solution up to 10 days or up to \$1000. (I already done reachability test before running the A*). IOW, the judge output must be a solution that is bigger than 10 days or bigger than \$1000 which is not allowed in the problem statement. Can anyone verify the judge output for this?

Lastly, what is the tricks?
I've spent too many WAs for this problem...
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
I got it Accepted... I forgot to clear the parent

The conversion for AM/PM to 24 hour is just like that and no judge output is > 10 days nor > \$10000.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

### Re:

sclo wrote:This problem can be solved by shortest path algorithms.
Did you use A* search??

I have no idea to use Dijkstra to solve this problem.
Because it may be 2 or above paths from one node to the other.

Finally I use backtracking and got AC.

I think it is easy to use backtracking to solve this problem with only 50 flights and 20 cities.

And an important thing is that if there are 2 or above optimal COST paths, I print one having both optimal TIME and COST.

122513
New poster
Posts: 1
Joined: Mon Apr 26, 2010 6:41 pm

### 205 getting there

Does anyone have come stricky cases for this problem or any test cases, i think its ok my program . I tried a lot and i can't find the bug and also I don't know how the total time has to displayed if there are less than 60 mins like 0:10 or 10

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

### Re: 205 - Getting There

I do a Dijkstra over a certain search space, where each state is a pair (p,t) -- place & current time.
d[(p,t)] is a structure that keeps the least amount of time spent to get into city p at time instant t, or, in case of equal amount of time spent, the least amount of money spent. (we are optimizing Time; Cost-case is analogous). The graph does not contain negative-cost edges (checked with assert),
and since the graph is acyclic, a Dijkstra or DP should work. However, WA. Could it be due to output formatting? My output matches that of udebug exactly.
Attaching my code in case anyone would want to have a look and comment

Code: Select all

``````/*
* 205. Getting There
* TOPIC: dp, dijkstra
* status:
*/
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 0x20
#define M 0x40
#define A 26
#define oo (1<<29)
#define xchg(x,y) (((x)==(y))||((x)^=(y),(y)^=(x),(x)^=(y)))
#define bubble (xchg(pos[heap[i]],pos[heap[j]]),xchg(heap[i],heap[j]))
#define tol 1e-12
#define DAY (24*60)
#define Q (1<<21)
#define enc(p,t) ((p)|((t)<<5))
typedef unsigned int state;

typedef struct cell {
struct cell *son[A];
int idx;
} cell;

cell pool[1<<21],*ptr = pool;
char buff[0x400],name[N][0x20],T[DAY+1][0x10];
state heap[Q<<1];
unsigned int p[Q];

cell *init() {
cell *x = ptr++;
int i;
for ( x->idx = -1, i = 0; i < A; x->son[i++] = NULL );
return x;
}

int push( cell *root, char *s ) {
cell *x,*y;
char *p = s;
for ( x = root; x && *s; x=x->son[*s++-'a'] )
if ( !x->son[*s-'a'] )
x->son[*s-'a'] = init();
if ( x->idx >= 0 ) return x->idx;
deg[n] = 0, strcpy(name[n],p), name[n][0] = toupper(name[n][0]);
return x->idx = n++;
}

int find( cell *root, char *s ) {
cell *x,*y;
char *p = s;
for ( x = root; x && *s; x=x->son[*s++-'a'] )
if ( !x->son[*s-'a'] ) return -1;
if ( *s ) return -1;
if ( x->idx >= 0 ) return x->idx;
return -1;
}

typedef struct {
int x,y,price,
st,duration;
char leave[0x10],arrive[0x10], pr[0x10];
} edge;

edge e[M];

typedef struct { int t,cost; } distance;

int cmp_by_time( const distance *a, const distance *b ) {
if ( a->t == b->t )
return a->cost-b->cost;
return a->t-b->t;
}

int cmp_by_cost( const distance *a, const distance *b ) {
if ( a->cost == b->cost )
return a->t-b->t;
return a->cost-b->cost;
}

typedef int (*func)( const distance*, const distance* );
func cmp[] = {cmp_by_time,cmp_by_cost};

distance d[Q];

void heap_push( state x, const int tt ) {
int i,j;
if ( inq[x] != yes )
pos[heap[cnt]=x] = cnt, ++cnt, inq[x] = yes;
for ( j = pos[x]; j && cmp[tt](d+heap[i=(j-1)>>1],d+heap[j]) > 0; bubble, j = i );
}

state pop( const int tt ) {
int i,j;
state x=*heap;
if ( cnt+=(pos[x]=-1) )
pos[*heap=heap[cnt]] = 0;
for ( inq[x]=0, j=0; (i=j,j<<=1,++j)<cnt; bubble ) {
if ( j<cnt-1 && cmp[tt](d+heap[j+1],d+heap[j]) < 0 ) ++j;
if ( cmp[tt](d+heap[i],d+heap[j]) <= 0 ) break ;
}
return x;
}

void reg( state *b, state u, int dst, int tt ) {
if ( (u&31UL) != dst ) return ;
if ( *b == -1 || cmp[tt](d+*b,d+u) > 0 )
*b = u;
}

state dijkstra( int src, int dst, const int tt ) {
int x,y,i,j,k,l,t,o,curtime,ncurtime;
state u,v,best=-1;

for ( ++yes, cnt = 0, i = 0; i < deg[src]; ++i )
k = adj[src][i], u = enc(src,e[k].st), d[u].cost = d[u].t = 0, heap_push(u,tt), p[u] = -1;
for (++indeed;cnt;)
for(u=pop(tt),x=(u&31UL),outside[u]=indeed,reg(&best,u,dst,tt),curtime=(u>>5),o=curtime%DAY,i=0;i<deg[x]&&x!=dst;++i) {
if ( o <= t )
ad.t = d[u].t+(t-o)+e[k].duration, ncurtime = curtime+(t-o)+e[k].duration;
else
l = o-t, ad.t = d[u].t+(DAY-l)+e[k].duration, ncurtime = curtime+(DAY-l)+e[k].duration;
ad.cost = d[u].cost+e[k].price, v = enc(y,ncurtime);
continue ;
if ( inq[v] != yes ) d[v].t = d[v].cost = +oo;
if ( cmp[tt](&ad,d+v) < 0 ) {
/*assert( outside[v] != indeed );*/
d[v] = ad, heap_push(v,tt), p[v] = (k|(u<<6));
}
}
return best;
}

void dump( state u ) {
int i = (p[u]&63UL);
state v = p[u]>>6;
char tmp[0x10];
if ( p[u] == -1 ) return ;
dump(v);
sprintf(tmp,"\$%.2lf",e[i].price/100.00+tol);
printf("%-20s%-23s%-8s%-8s%7s\n",name[e[i].x],name[e[i].y],T[e[i].st],T[(e[i].st+e[i].duration)%DAY],tmp);
}

int main() {
int i,j,k,l,t,travelid,p0,p1,sh,sm,th,tm,ts=0,cs,days,rem;
char tmp[0x200],aa[0x20],bb[0x20],tmps[0x20],tmpt[0x20],SH[0x20],TH[0x20],price[0x20];
state u;
double w;
cell *root;
#ifndef ONLINE_JUDGE
freopen("205.in","r",stdin);
#endif
for ( i = 0; i <= 23; ++i )
for ( j = 0; j <= 59; ++j )
sprintf(T[k=i*60+j],"%d:%02d%c",i%12,j,i>=12?'P':'A');
for (;fgets(buff,sizeof buff,stdin) && 2==sscanf(buff,"%s %d",tmp,&travelid);) {
if ( ++ts > 1 ) puts("\n");
for ( n=0, m=0, ptr=pool, root=init(); fgets(buff,sizeof buff,stdin) &&\
5==sscanf(buff,"%s %s %s %s %s",aa,bb,SH,TH,price); adj[i][deg[i]++] = m++ ) {
sscanf(SH,"%d:%d%s",&sh,&sm,tmps);
sscanf(TH,"%d:%d%s",&th,&tm,tmpt);
assert( sh < 12 );
assert( th < 12 );
/*sscanf(price,"%d.%d",&p0,&p1);*/
sscanf(price,"%lf",&w);
assert( w > 0 );
for ( i=0; aa[i]; aa[i]=tolower(aa[i]), ++i );
for ( i=0; bb[i]; bb[i]=tolower(bb[i]), ++i );
e[m].x = i = push(root,aa), e[m].y = j = push(root,bb);
e[m].st = sh*60+sm+(0[tmps]=='A'?0:DAY/2);
k = th*60+tm+(0[tmpt]=='A'?0:DAY/2);
e[m].duration = k>=e[m].st?k-e[m].st:DAY-e[m].st+k;
/*e[m].price = p0*100+p1;*/
e[m].price = (int)(100*w+tol);
strcpy(e[m].leave,SH);
strcpy(e[m].arrive,TH);
e[m].pr[0]='\$',strcpy(e[m].pr+1,price);
}
printf("Requests and optimal routes for travel %d\n------------------------------------------\n\n",travelid);
for ( cs = 0; fgets(buff,sizeof buff,stdin) && 3==sscanf(buff,"%s %s %s",aa,bb,tmp); ) {
if ( ++cs > 1 ) putchar('\n');
for ( i=0; aa[i]; aa[i]=tolower(aa[i]), ++i );
for ( i=0; bb[i]; bb[i]=tolower(bb[i]), ++i );
i = find(root,aa), j = find(root,bb);
0[aa] = toupper(0[aa]), 0[bb] = toupper(0[bb]);
if ( 0 == strcmp(aa,bb) ) {
continue ;
}
if ( i == -1 || j == -1 ) {
printf("There is no route from %s to %s.\n",aa,bb);
continue ;
}
for ( 0[tmp] = toupper(0[tmp]), k = 1; tmp[k]; tmp[k] = tolower(tmp[k]), ++k );
switch ( tolower(0[tmp]) ) {
case 'c': u = dijkstra(i,j,1); break ;
case 't': u = dijkstra(i,j,0); break ;
default: assert(0);
}
if ( i == j ) {
continue ;
}
if ( u == -1 ) {
printf("There is no route from %s to %s.\n",name[i],name[j]);
continue ;
}
printf("%-4s: %-17s%6s: %-17s%12s: %s\n","From",aa,"To",bb,"Optimize",tmp);
puts("==================================================================");
puts("From                To                     Leave   Arrive     Cost");
puts("==================================================================");
dump(u), puts("                                           -----------------------");
days = d[u].t/DAY, rem = d[u].t%DAY;
if ( days == 1 )
sprintf(tmp,"1 day %d:%02d",rem/60,rem%60);
else if ( days >= 2 )
sprintf(tmp,"%d days %d:%02d",days,rem/60,rem%60);
else sprintf(tmp,"%d:%02d",rem/60,rem%60);
printf("%57s",tmp), sprintf(tmp,"\$%.2lf",d[u].cost/100.00+tol),
printf("%9s\n",tmp);
}
}
return 0;
}

``````

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

### Re: 205 - Getting There

What is the correct output for

Code: Select all

``````TRAVEL  35
yuqywldlcf mbspttle 07:29A 04:35A 0.84
etwuuug bukxeuwmrnr 11:07A 07:10A 1.54
powpc bukxeuwmrnr 06:47P 03:31P 0.65
rpjjkbsjfrhidp fzkkbxopfi 03:56A 08:28A 9.36
etwuuug mbspttle 09:57P 02:31P 8.02
bukxeuwmrnr nangtq 05:10A 06:10A 1.52
flpsfgkmje mxzdrwv 03:45P 07:45A 9.14
odalfopkthgxedt bukxeuwmrnr 11:43A 05:04P 5.69
powpc rpjjkbsjfrhidp 11:07P 04:56P 13.56
qdzbvbsjtt rpjjkbsjfrhidp 02:13A 05:18P 11.44
mxzdrwv odalfopkthgxedt 08:25A 10:39P 8.81
etwuuug nangtq 11:46P 09:10A 2.54
yuqywldlcf acbaoylqkzxxcb 02:23P 03:42P 5.53
bnratvha powpc 11:36P 07:19P 13.05
hbguzqywywqkkn bnratvha 07:38A 03:34A 6.91
powpc nangtq 00:20P 05:04P 13.10
nwjdeshqsusfhc lblwhsqwj 08:25A 09:11A 13.56
odalfopkthgxedt mxzdrwv 09:01P 05:26P 9.36
mxzdrwv nwjdeshqsusfhc 07:49P 11:34P 6.31
mxzdrwv nangtq 06:50A 10:39P 12.87
flpsfgkmje yuqywldlcf 01:13A 01:45A 8.04
bukxeuwmrnr yuqywldlcf 04:27P 02:13P 4.39
rpjjkbsjfrhidp acbaoylqkzxxcb 07:22A 05:18A 8.74
giqkhedpgbgiix yuqywldlcf 05:52A 01:53P 0.13
qdzbvbsjtt nwjdeshqsusfhc 00:57A 00:22A 12.48
flpsfgkmje etwuuug 07:09A 09:52A 5.71
odalfopkthgxedt etwuuug 00:46P 02:23P 8.95
giqkhedpgbgiix rpjjkbsjfrhidp 00:39A 05:56P 13.73
fzkkbxopfi bnratvha 02:10P 06:09A 12.09
bukxeuwmrnr mbspttle 10:25P 02:24A 9.58
bukxeuwmrnr mxzdrwv 02:59P 00:16A 3.31
yuqywldlcf mxzdrwv 11:05P 06:28P 6.23
hbguzqywywqkkn etwuuug 03:15A 00:43A 5.11
yuqywldlcf qdzbvbsjtt 07:14A 01:25A 6.90
dygzwngdaz flpsfgkmje 06:13P 06:12A 0.07
hbguzqywywqkkn giqkhedpgbgiix 05:18A 06:03A 1.41
odalfopkthgxedt rpjjkbsjfrhidp 04:55P 07:31P 3.80
odalfopkthgxedt giqkhedpgbgiix 00:24A 11:50A 0.45
bnratvha odalfopkthgxedt 07:13P 09:37A 9.14
giqkhedpgbgiix lblwhsqwj 04:11A 05:20A 9.00
powpc nwjdeshqsusfhc 10:45P 06:25A 1.43
nangtq giqkhedpgbgiix 11:01A 03:11P 9.33
lblwhsqwj odalfopkthgxedt 00:05A 04:18P 13.27
nangtq powpc 10:53P 04:30A 9.42
giqkhedpgbgiix bnratvha 08:28A 11:18A 5.69
lblwhsqwj mxzdrwv 11:22A 09:35A 5.33
rpjjkbsjfrhidp giqkhedpgbgiix 06:26A 01:11A 1.85
rpjjkbsjfrhidp fzkkbxopfi 03:39P 09:30P 8.39
bnratvha nwjdeshqsusfhc 03:03P 07:17P 6.74
#
rpjjkbsjfrhidp etwuuug TIME
odalfopkthgxedt dygzwngdaz COST
lblwhsqwj qdzbvbsjtt COST
#
TRAVEL  192
jvpea qlddh 03:20A 06:25P 2.86
dhcxambywi dws 07:26P 04:44P 5.23
kahmbwyhw wma 06:59P 03:22A 5.06
kahmbwyhw hfcfjvws 01:16P 00:39P 5.15
znkyl dgafpgd 00:04A 10:54P 9.88
dhcxambywi jvpea 10:55A 04:11A 9.81
pyuveebif dws 09:29A 08:07A 4.23
pyuveebif dws 01:44A 11:16P 6.37
uauyswxiwhwowbqr pxcfjplosugtkb 08:03A 07:59A 7.83
hfcfjvws kahmbwyhw 05:38P 06:24A 8.51
qlddh dgafpgd 00:11P 04:14P 6.45
irednbdrvlbhhfl fiolu 09:18P 02:13P 9.10
fiolu kahmbwyhw 04:54A 08:11A 7.39
gkrfhvmpqb qlddh 04:48P 02:52A 9.86
clkymcbm hfcfjvws 03:02P 01:33A 5.66
dgafpgd irednbdrvlbhhfl 04:34P 03:02A 7.38
dgafpgd dhcxambywi 05:52A 05:43P 8.36
dgafpgd dws 00:15A 01:40A 4.90
dws gkrfhvmpqb 04:43A 03:40P 7.30
icekppvav pxcfjplosugtkb 08:43P 07:50P 3.15
jvpea icekppvav 05:59P 02:54P 8.32
fiolu kahmbwyhw 08:21P 04:15A 9.12
znkyl dgafpgd 03:10A 09:09P 0.49
icekppvav kahmbwyhw 02:45P 06:47P 13.71
qlddh gkrfhvmpqb 10:32A 08:53A 5.53
wma gkrfhvmpqb 06:21P 05:16P 8.31
wma uauyswxiwhwowbqr 02:13P 10:26P 4.59
jvpea qlddh 08:57A 10:04A 8.61
jvpea dhcxambywi 11:05A 06:30A 9.73
dhcxambywi pxcfjplosugtkb 02:00P 01:09A 9.80
uauyswxiwhwowbqr clkymcbm 03:26P 05:40P 2.73
irednbdrvlbhhfl hfcfjvws 10:49P 07:54A 3.58
updbaiu gkrfhvmpqb 02:28A 00:29A 6.51
wma znkyl 11:20A 01:00A 13.91
qlddh znkyl 06:48P 07:08P 6.63
wnnh gkrfhvmpqb 11:14A 00:34P 0.42
dws icekppvav 04:59P 03:17A 1.78
fiolu dgafpgd 05:34A 07:37A 3.02
qlddh dgafpgd 03:35A 06:56P 1.15
dhcxambywi znkyl 03:27A 00:11A 6.63
znkyl pyuveebif 04:15P 09:25A 3.23
dws kahmbwyhw 11:20A 09:45P 10.69
uauyswxiwhwowbqr pyuveebif 03:50P 01:44P 9.10
gkrfhvmpqb jvpea 07:52P 06:30P 12.15
hfcfjvws wma 08:39P 09:32P 12.82
irednbdrvlbhhfl hfcfjvws 07:35P 03:19A 5.24
uauyswxiwhwowbqr wnnh 08:58A 07:46P 6.90
znkyl irednbdrvlbhhfl 03:29A 00:46A 10.22
znkyl fiolu 09:34A 00:30P 10.66
#
dgafpgd dws COST
wma hfcfjvws TIME
znkyl pyuveebif TIME
#
TRAVEL  52
gshjtdsbcsorpixe qkxfkmstd 08:02P 06:36P 12.85
ffbiuurrsvvmcph qurgkzkyyktepmah 05:38P 08:43P 1.15
gshjtdsbcsorpixe qkxfkmstd 04:38P 09:47A 7.27
cfxhpkjpsejs ffbiuurrsvvmcph 03:22P 09:34P 9.73
ffbiuurrsvvmcph qkxfkmstd 06:09A 00:44P 1.40
akp vwbgifha 10:33P 11:07P 1.06
gshjtdsbcsorpixe curilkkbdq 06:22A 09:26P 6.28
vwbgifha csss 09:53P 03:34P 8.82
dqmiwr gshjtdsbcsorpixe 04:37A 10:45P 5.60
ceexnchyydwhkklq qurgkzkyyktepmah 05:55P 07:17A 4.04
ffbiuurrsvvmcph yzthchsyuzfdzb 08:16P 00:34P 4.97
ffbiuurrsvvmcph vkxmylsvnsg 02:32A 03:49A 4.64
gshjtdsbcsorpixe dqmiwr 11:38A 03:51P 3.37
ffbiuurrsvvmcph idviwzzogshhio 07:36P 11:18A 0.50
ceexnchyydwhkklq qkxfkmstd 03:41A 04:58A 11.79
csss vwbgifha 06:30A 09:20A 3.08
gshjtdsbcsorpixe jqffusfgklnhiuv 03:52P 05:37A 6.18
hqthioe vwbgifha 08:33A 04:55A 2.37
cfxhpkjpsejs idviwzzogshhio 02:25A 02:11A 11.30
csss qurgkzkyyktepmah 01:51P 03:26P 6.91
vwbgifha cfxhpkjpsejs 11:54A 10:59P 4.41
qkxfkmstd akp 05:55P 07:39P 13.07
jqffusfgklnhiuv vwbgifha 09:38A 02:00P 4.72
qkxfkmstd gshjtdsbcsorpixe 06:01P 10:35P 5.65
ceexnchyydwhkklq csss 03:38P 10:04A 11.40
curilkkbdq gshjtdsbcsorpixe 10:14A 02:16A 11.84
vwbgifha ffbiuurrsvvmcph 01:44P 08:38P 2.72
ceexnchyydwhkklq vkxmylsvnsg 03:52P 04:40P 12.91
qkxfkmstd vkxmylsvnsg 11:03P 10:51P 8.04
yzthchsyuzfdzb ceexnchyydwhkklq 00:53A 02:58P 12.73
yzthchsyuzfdzb idviwzzogshhio 10:24P 02:31P 1.82
cfxhpkjpsejs jqffusfgklnhiuv 00:48P 07:25P 11.66
qurgkzkyyktepmah ceexnchyydwhkklq 00:49A 04:28A 7.36
dqmiwr idviwzzogshhio 07:56A 02:26P 5.04
ffbiuurrsvvmcph jqffusfgklnhiuv 05:46A 07:37P 6.60
qkxfkmstd cfxhpkjpsejs 11:13P 02:45A 9.87
ffbiuurrsvvmcph idviwzzogshhio 02:04P 09:03A 9.89
jqffusfgklnhiuv qurgkzkyyktepmah 02:20P 02:08P 10.83
idviwzzogshhio qurgkzkyyktepmah 11:52P 08:30P 0.03
zcuutguqpvl jrklbaficvnsyh 03:16A 10:29P 6.19
qurgkzkyyktepmah vkxmylsvnsg 07:35A 00:52A 9.44
vjhiwciebnzdwtex ffbiuurrsvvmcph 06:33P 05:47P 12.31
jrklbaficvnsyh qkxfkmstd 00:33P 07:35A 12.15
csss dqmiwr 08:14A 05:13A 9.42
vkxmylsvnsg akp 06:48P 08:56P 0.33
qkxfkmstd vkxmylsvnsg 04:01P 00:18A 11.96
vwbgifha jrklbaficvnsyh 04:22A 11:06P 11.09
ffbiuurrsvvmcph yzthchsyuzfdzb 06:42A 10:43P 0.70
jrklbaficvnsyh ceexnchyydwhkklq 01:20A 11:13A 6.94
#
jrklbaficvnsyh yzthchsyuzfdzb COST
gshjtdsbcsorpixe vwbgifha COST
yzthchsyuzfdzb csss TIME
#``````
For this randomly-generated test, udebug outputs "Invalid input", although why it is so I can't make out.