157 - Route Finding

[ftomi]

Hello!

Can anybody tell me the output for this input? Thanks

Code: Select all

4
A:a=Ba=Ca
B:ab
C:ab
D:ab=Cb
AaCa
AaAa
AaCb
AaDb
BbCb
#

[Ivan Golubev]

Output:
3: Aa=Ca
0: Aa
4: Aa=Cab
7: Aa=Cab=Db
5: Bba=Cab

[ftomi]

I thought, "Connecting stations will have more than one designation" means I should not change line If I start at a 'connecting station', but not that line, what should I use. It would be closer to the real life...
Thanks!

[Caesum]

My program gives the correct answers for all of the examples and the cases quoted here and yet I still get a WA. I have tried all of the test cases I can think of, along similar lines to those here and can't find anything wrong. Does anyone have a more complete/complex test case I can try ?

[Caesum]

I am still no nearer solving this. I really can't see where this is going wrong, here is my code:

[c]
deleted..... doesnt need to be here now
[/c]

[xenon]

I have no C-compiler at hand, so I did a little 'mind-debugging'.

Consider the input:
3
A:a=Cabcdefg=Bb
B:a=Cbb=Ag
C:a=Aab=Ca
BbAa
#

The correct answer is:
8:Bba=Cba=Aa
but I think your program produces:
8:Bb=Agfedcba

Your floodfill fills mtime['Ag'] with 6 and mtime['Ba'] with 7. Both values are correct, but the correct route is via the higher mtime['Ba'], while your routefinder selects the lower mtime['Ag'].

I hope I have made no mistakes. I haven't solved the problem yet, so I have no way of checking my assumptions...

[Caesum]

it gives
8: Bba=Cba=Aa

btw, hi xenon

oh, and it does say:
Note that there will always be only one fastest route for any given pair of stations.
in the question.

[xenon]

hi yourself!
't was just a thought.
Sure, there is only one shortest route in the input I made up, the route via 'Ag' is longer (9) then via 'Ba' (8). I just didn't see your routefinder rule out traveling from 'Bb' (mtime=8) to 'Ag' (mtime=6), since conn['Bb']['Ag']==1 (it's a station), while the actual time is 3 seconds.
Nevermind.
Thx for putting a link to this contest on your site. I'm completely hooked eversince... :)

[Caesum]

thanks xenon,
you saved me
your idea was right in principle, when i was backtracing the route it was possible for one to have lower time but not be part of the final route since it had to be either 3 less or 1 less and in the same major section to be on the route. solved now i just need to get rid of a few more wa's.......

[xenon]

Guess it's enough either to save an extra predecessor field while floodfilling, then backtracking always gives the correct route, or recheck the moves while stepping back, and then your code will work. I'll take the liberty to leech your program (is to leech an english verb?), of which I saved a copy , and translate your ideas into pascal, and submit it as my own
Happy hunting!

[Caesum]

Actually, i just made two checks: either the step back reduces the cost by 3, or it reduces the cost by 1 and is on the same major route. No, I dont mind, it helps save time

[xenon]

In the end i decided to start anew and try something Dijkstra-ish. Took me 3 hours to implement it . But it got accepted and runs twice as fast using twice as much memory. Still wonder how the other guys can do it in zero CPU-time with 64k memory.
TTYL - xenon

[pokute]

1
A:fgmpnxzabjdf
AaAa
#



What is the correct answer?

0: Aa
or
0: Aaa
or
2: Aaba


This is my code..

[cpp]
#include <iostream>
#include <iomanip>

using namespace std;

struct edge
{
int w;
char prevRoute, prevStation;
} graph[26][26][26][26];

bool route[26], station[26][26];
char buff[256], *pBuff, *p2Buff, *p3Buff;

void prnPath(int i, int j, int k, int l);

void main()
{
int i, j, k, l, m, n;

for(i = 0; i < 26; i++)
{
route = false;
for(j = 0; j < 26; j++)
{
station[j] = false;
for(k = 0; k < 26; k++)
{
for(l = 0; l < 26; l++)
{
graph[j][k][l].w = 0;
graph[j][k][l].prevRoute = -1;
graph[j][k][l].prevStation = -1;
}
}
}
}

for(cin >> i; i > 0; i--)
{
for(cin.getline(buff, 256); buff[0] == '\0'; cin.getline(buff, 256));
pBuff = buff + 2;
route[(j = buff[0] - 'A')] = true;

for(pBuff = buff + 3, k = buff[2] - 'a', station[j][k] = true; *pBuff != '\0'; pBuff++)
{
if(*pBuff == '=')
{
p2Buff = pBuff + 1;
do
{
route[(l = *(++pBuff) - 'A')] = true;
station[l][(m = *(++pBuff) - 'a')] = true;
graph[j][k][l][m].w = graph[l][m][j][k].w = 3;

for(p3Buff = p2Buff; p3Buff < pBuff - 1; p3Buff += 3)
graph[p3Buff[0] - 'A'][p3Buff[1] - 'a'][l][m].w = graph[l][m][p3Buff[0] - 'A'][p3Buff[1] - 'a'].w = 3;
} while(*(++pBuff) == '=');

if(*pBuff == '\0')
break;
}

if('a' <= *pBuff && *pBuff <= 'z')
{
station[j][(l = *pBuff - 'a')] = true;
graph[j][k][j][l].w = graph[j][l][j][k].w = 1;
k = l;
}
}
}

for(i = 0; i < 26; i++)
{
if(route)
{
for(j = 0; j < 26; j++)
{
if(station[j])
{
for(k = 0; k < 26; k++)
{
if(route[k])
{
for(l = 0; l < 26; l++)
{
if(/*!(i == k && j == l) && */station[k][l] && graph[k][l][j].w)
{
for(m = 0; m < 26; m++)
{
if(route[m])
{
for(n = 0; n < 26; n++)
{
if(/*!(k == m && l == n) && !(i == m && j == n) && */station[m][n] && graph[j][m][n].w)
{
if(graph[k][l][m][n].w == 0 || graph[k][l][m][n].w > graph[k][l][j].w + graph[i][j][m][n].w)
{
graph[k][l][m][n].w = graph[k][l][i][j].w + graph[i][j][m][n].w;
graph[k][l][m][n].prevRoute = i;
graph[k][l][m][n].prevStation = j;
}
}
}
}
}
}
}
}
}
}
}
}
}

while(cin.getline(buff, 256))
{
if(buff[0] == '#')
break;

i = buff[0] - 'A';
j = buff[1] - 'a';
k = buff[2] - 'A';
l = buff[3] - 'a';

cout << setw(3) << graph[i][j][k][l].w << ": ";
pBuff = buff;
prnPath(i, j, k, l);
*(pBuff++) = k +'A';
*(pBuff++) = l +'a';
*pBuff = '\0';

cout << buff[0] << buff[1];
for(pBuff = buff + 2; *pBuff != '\0'; pBuff += 2)
{
if(*pBuff == *(pBuff - 2))
cout << *(pBuff + 1);
else
cout << '=' << *pBuff << *(pBuff + 1);
}
cout << endl;
}
}

void prnPath(int i, int j, int k, int l)
{
if(graph[i][j][k][l].prevRoute == -1)
{
*(pBuff++) = i +'A';
*(pBuff++) = j +'a';
}
else
{
prnPath(i, j, graph[i][j][k][l].prevRoute, graph[i][j][k][l].prevStation);
prnPath(graph[i][j][k][l].prevRoute, graph[i][j][k][l].prevStation, k, l);
}
}
[/cpp]

[Pedrinho UFPE]

Still WA

[little joey]

My accepted program gives a different answer for ftomi's example:

Code: Select all

  3: Aa=Ca
  6: Aa
  4: Aa=Cab
  7: Aa=Cab=Db
  5: Bba=Cab

while your program reproduces the (wrong) output of Ivan Golubev.