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
Code: Select all
1
A B 24 6
A B
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.
Code: Select all
1
A B 24 3
A B
Code: Select all
1
1
A B 24 6
A B
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.
Code: Select all
cut after AC...
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;
}