Posted:

**Sat Apr 08, 2006 10:12 am**The following page has some information about the restricted packages:

http://acm.uva.es/problemset/java.html

http://acm.uva.es/problemset/java.html

Page **2** of **4**

Posted: **Sat Apr 08, 2006 10:12 am**

The following page has some information about the restricted packages:

http://acm.uva.es/problemset/java.html

http://acm.uva.es/problemset/java.html

Posted: **Tue Mar 20, 2007 2:18 pm**

What's outpyut for this:

Code: Select all

```
1
A B 24 6
A B
```

Posted: **Tue Mar 20, 2007 4:40 pm**

My accepted code returnsserur wrote:Code: Select all

`1 A B 24 6 A B`

Code: Select all

```
Test Case 1.
Vladimir needs 0 litre(s) of blood.
```

Posted: **Thu Mar 22, 2007 9:03 am**

Ok, thanks Jan. If
should be 1 litre?

Code: Select all

```
1
A B 24 3
A B
```

Posted: **Thu Mar 22, 2007 9:25 am**

Posted: **Thu Mar 22, 2007 9:32 am**

Sorry, but I can't see why. Why he can't start at midnight (00.00 AM) and arrive at B at 03.00 AM?

Posted: **Thu Mar 22, 2007 9:54 am**

Sorry for the outputs I have posted. I have corrected both outputs. The reason for posting wrong output is simple

It is the correct input format. I just copied your input and ran my code . So, the outputs were wrong.

Code: Select all

```
1
1
A B 24 6
A B
```

Posted: **Sat Mar 24, 2007 2:36 pm**

Thanks, Jan.

I implemented shortest path in 0-1 graphs, but still can't get it right.

I implemented shortest path in 0-1 graphs, but still can't get it right.

Posted: **Sun Mar 25, 2007 10:01 am**

Try the cases...

**Input:**
**Output:**
Hoe these help.

Code: Select all

```
2
3
Dhk Ctg 1 2
Ctg Syl 2 3
Syl Mym 4 5
Dhk Syl
3
Dhk Ctg 18 19
Ctg Syl 19 20
Syl Mym 21 22
Dhk Ctg
```

Code: Select all

```
Test Case 1.
Vladimir needs 1 litre(s) of blood.
Test Case 2.
There is no route Vladimir can take.
```

Posted: **Fri Jul 27, 2007 8:15 am**

My code gets WA several times. Can someone tell me why??

Thanks.

Code: Select all

```
cut after AC...
```

Posted: **Fri Nov 09, 2007 7:10 am**

I am trying to solve this problem using the following approach:

1. For each route (city1 city2 departure_time travelling_time):

a) if departure_time lies between 18 and 24, departure_time -= 18

b) if departure_time lies between 1 and 6, departure_time += 6

c) else ignore route.

after these steps the following mapping has been made:

18 -> 0 1 -> 7

19 -> 1 2 -> 8

20 -> 2 3 -> 9

21 -> 3 4 -> 10

22 -> 4 5 -> 11

23 -> 5 6 -> 12

24 -> 6

if departure_time + travelling_time <= 12 then the train arrives before 6AM and the route must be added to the list of routes available from city1, else ignore route.

2. After that I try to generate every possible path from starting_city to destination_city using recursion taking into account that:

if the time at which I arrive to a city <= departure_time of a route the vampire does not have to drink blood, else he must drink one litre.

Is there anything wrong in that?

This is my code... It would be very helpful if you find some input that makes my program fail.

1. For each route (city1 city2 departure_time travelling_time):

a) if departure_time lies between 18 and 24, departure_time -= 18

b) if departure_time lies between 1 and 6, departure_time += 6

c) else ignore route.

after these steps the following mapping has been made:

18 -> 0 1 -> 7

19 -> 1 2 -> 8

20 -> 2 3 -> 9

21 -> 3 4 -> 10

22 -> 4 5 -> 11

23 -> 5 6 -> 12

24 -> 6

if departure_time + travelling_time <= 12 then the train arrives before 6AM and the route must be added to the list of routes available from city1, else ignore route.

2. After that I try to generate every possible path from starting_city to destination_city using recursion taking into account that:

if the time at which I arrive to a city <= departure_time of a route the vampire does not have to drink blood, else he must drink one litre.

Is there anything wrong in that?

This is my code... It would be very helpful if you find some input that makes my program fail.

Code: Select all

```
#include <stdio.h>
#include <string.h>
#define MAXVERT 100
#define MAXEDGE 1000
#define LEN 32
#define INF 1000000
typedef struct aruta
{
int final;
int hora_salida;
int hora_llegada;
} ruta;
int n, ini, fin, min;
char ciudad[MAXVERT + 1][LEN + 1];
int grado[MAXVERT + 1];
ruta mat[MAXVERT + 1][MAXEDGE + 1];
bool mark[MAXVERT + 1];
int buscar_ciudad(const char *key)
{
for (int i = 1; i <= n; i++)
if (strcmp(key, ciudad[i]) == 0)
return i;
return 0;
}
void go(int nodo, int time, int cons)
{
if (cons > min)
return;
if (nodo == fin)
{
if (cons < min)
min = cons;
return;
}
for (int i = 1; i <= grado[nodo]; i++)
{
int final, hora_salida, hora_llegada;
final = mat[nodo][i].final;
hora_salida = mat[nodo][i].hora_salida;
hora_llegada = mat[nodo][i].hora_llegada;
if (!mark[final])
{
mark[final] = true;
if (time <= hora_salida)
go(final, hora_llegada, cons);
else
go(final, hora_llegada, cons + 1);
mark[final] = false;
}
}
}
int main()
{
int test;
scanf("%d", &test);
for (int tt = 1; tt <= test; tt++)
{
int nr, index1, index2, hs, td;
char s1[LEN + 1], s2[LEN + 1];
printf("Test Case %d.\n", tt);
scanf("%d", &nr);
n = 0;
while (nr--)
{
scanf("%s %s %d %d", &s1, &s2, &hs, &td);
index1 = buscar_ciudad(s1);
if (index1 == 0)
{
index1 = ++n;
grado[n] = 0;
strcpy(ciudad[n], s1);
}
index2 = buscar_ciudad(s2);
if (index2 == 0)
{
index2 = ++n;
grado[n] = 0;
strcpy(ciudad[n], s2);
}
if (hs >= 18 && hs <= 24)
{
hs -= 18;
}
else
if (hs >= 1 && hs <= 6)
{
hs += 6;
}
else
continue;
if (hs + td <= 12)
{
grado[index1]++;
mat[index1][ grado[index1] ].final = index2;
mat[index1][ grado[index1] ].hora_salida = hs;
mat[index1][ grado[index1] ].hora_llegada = hs + td;
// printf("%d -> %d HS=%d HL=%d\n", index1, index2, hs, hs + td);
}
}
scanf("%s %s", &s1, &s2);
ini = buscar_ciudad(s1);
fin = buscar_ciudad(s2);
if (ini && fin)
{
for (int i = 1; i <= n; i++)
mark[i] = false;
min = INF;
mark[ini] = true;
go(ini, 0, 0);
if (min != INF)
{
printf("Vladimir needs %d litre(s) of blood.\n", min);
}
else
{
puts("There is no route Vladimir can take.");
}
}
else
{
puts("There is no route Vladimir can take.");
}
}
return 0;
}
```

Posted: **Fri Jan 25, 2008 10:00 am**

Other question:

If the train arrives, let say at 22 and another leaves at 22 (same hour), are we able to leave with the second train??

If the train arrives, let say at 22 and another leaves at 22 (same hour), are we able to leave with the second train??

Posted: **Fri Jan 25, 2008 3:27 pm**

getting wrong answer a lot of times and finally ACCEPTED!!!

i think it is a normal bfs problem but the starting time doesn't have a range, namely the starting time can be very large, more than 24, so after you read the starting time,**you need to mod 24**, and then judge wheter it is <=6 or >=18. if starting time is out of this range, Vladimir surely couldn't take this train.

to micmix, yes, it is available to take more than one train at the same day, and consider Vladimir can change to another train immediately, i.e. don't need any time.

i think it is a normal bfs problem but the starting time doesn't have a range, namely the starting time can be very large, more than 24, so after you read the starting time,

to micmix, yes, it is available to take more than one train at the same day, and consider Vladimir can change to another train immediately, i.e. don't need any time.

Posted: **Sat Jan 26, 2008 2:57 pm**

I've implemented it using dijkstra algorithm. It works fine with all test data posted in this thread. I've tried 1000 connections and 100 towns, yet it still gets WA. I think that it may be because of No connections, but I'm not shure. Anyone has any wierd test data with wrong connections that may be incorrectly accepted??

Posted: **Thu Jun 26, 2008 2:02 pm**

no.. we must not mod the departing time with 24... mine didn't use any mod and still AC... so just use the "> 6 or < 18" rule of range for the departing time... ^^