Page **3** of **3**

Posted: **Mon Aug 23, 2004 6:27 am**

by **sohel**

Accepted.

I modified my bfs() and got it AC in 0.04 seconds.

Larry wrote:
Use dynamic programming by first finding a recurrence..

Can someone give some detail about this recurrence relation. I think most of the people used Larry's method.

Posted: **Mon Aug 23, 2004 3:59 pm**

by **tep**

I use memoization / dp approach. Here is some clue

memo[v][d]

can i reach the destination if i'm vertex no v and i have d days left.

I'm sure you can figure out the rest

regards,

stephanus

### 10681 Teobaldo's Trip

Posted: **Thu Sep 01, 2005 4:16 am**

by **daveon**

Here is a tricky case.

INPUT:

OUTPUT:

### 10681 Problem..

Posted: **Fri Nov 25, 2005 6:30 am**

by **Rocky**

I Get WA For This Problem....

Can Any One Give Me Some Tricky Case.....

Thank's In Advance

Rocky

Posted: **Mon Dec 26, 2005 12:50 am**

by **daveon**

### Thank's..

Posted: **Sun Jan 01, 2006 7:15 am**

by **Rocky**

Thank's....

Rocky

### 10681 Teobaldo's Trip again.. Tell me what's wrong..!!

Posted: **Thu Jan 05, 2006 6:01 pm**

by **helloneo**

if Teobaldo can go j city on i-th day, i check dp[j]

* = i*

it's kind of straightforward.. but getting WA..

plz tell me what's wrong..

### Try this input

Posted: **Sun Feb 19, 2006 6:29 pm**

by **medv**

Try this input:

2 1

1 2

1 2 3

your program gives NO, but must be YES.

The trip is: 1 - 2 - 1 - 2

Posted: **Sat Apr 01, 2006 9:55 am**

by **asif_rahman0**

i m not expert in DP

so i think u can use easily matrix multiplication for finding link between vertices. which is O(n^3).

then use another loop for days....then it would be O(n^4) by some extra checking. get it aceepted within 1.4/1.3

hope it helpssssssss.

**N.B: dont use map[days]***[j] = map[days]**[j] | ( map[days]**[k]&map[days][k][j])*

use IF condition for faster Running Time

Posted: **Fri Aug 04, 2006 11:31 pm**

by **Darko**

I guess I don't understand this problem...

What would be the output for

I think it's "No", because he can't make that trip in exactly 4 days?

Posted: **Sat Aug 05, 2006 12:02 am**

by **mf**

That's right. Output is "No" if and only if there is no trip of length exactly D days.

### Re: 10681 - Teobaldo's Trip

Posted: **Tue Jun 07, 2011 10:19 pm**

by **Shafaet_du**

I solved using dp but i am interested to know the matrix exponent solution. I am failing to raise the power to 200 as the elements are becoming too large. Do we need to use some kind of modular arithmetic?

### Re: 10681 - Teobaldo's Trip

Posted: **Wed Jul 25, 2012 10:49 pm**

by **pranon**

Code being judged ``WA" with me having no idea why. Any help in pointing out would be much appreciated.

Code: Select all

```
[code]
#include <stdio.h>
#include <string.h>
char mat[105][105], adj[105][105], temp[105][105], city[105];
char ytic[100000];
int main()
{
int c, l, j, i, a, b, s, e, d, t, k;
while(scanf("%d %d", &c, &l)==2 && (c || l))
{
j=0;
while(l--)
{
scanf("%d %d", &a, &b);
if(ytic[a]==0)
{
city[j]=a;
ytic[a]=j++;
}
if(ytic[b]==0)
{
city[j]=b;
ytic[b]=j++;
}
adj[ytic[a]][ytic[b]]=adj[ytic[b]][ytic[a]]=mat[ytic[a]][ytic[b]]=mat[ytic[b]][ytic[a]]=1;
}
scanf("%d %d %d", &s, &e, &d);
t=1;
s=ytic[s];
e=ytic[e];
while((t<<1)<=d)
{
for(i=0; i<c; i++)
for(j=0; j<c; j++)
for(k=0; k<c; k++)
if(mat[i][k]>0 && mat[k][j]>0)
temp[i][j]=1;
for(i=0; i<c; i++)
for(j=0; j<c; j++)
mat[i][j]=temp[i][j];
t<<=1;
}
while(t<d)
{
for(i=0; i<c; i++)
for(j=0; j<c; j++)
for(k=0; k<c; k++)
if(mat[i][k]>0 && adj[k][j]>0)
temp[i][j]=1;
for(i=0; i<c; i++)
for(j=0; j<c; j++)
mat[i][j]=temp[i][j];
t++;
}
(mat[s][e]>0 ||(s==e && d==0))?printf("Yes, Teobaldo can travel.\n"):printf("No, Teobaldo can not travel.\n");
for(i=0; i<c; i++)
{
memset(mat[i], 0, c*sizeof(char));
memset(adj[i], 0, c*sizeof(char));
}
memset(city, 0, c*sizeof(char));
}
return 0;
}
```

[/code]

Thanks in advance.

### Re: 10681 - Teobaldo's Trip

Posted: **Thu Feb 14, 2013 12:29 am**

by **mostafiz93**

I'm getting WA in this problem.

My algo is : first make adjacency matrix with the given liunks. then journey is possible if [adj matrix]^d is nonzero.

i've implemented this with matrix exponentiation.

Can anybody help me?

my code is here:

### Re: 10681 - Teobaldo's Trip

Posted: **Thu Jul 24, 2014 7:54 am**

by **sdipu**

When you are solving this problem using matrix exponentiation, don't forget to use modulo operation.

Try this-

input:

Code: Select all

```
3 2
1 2
2 3
3 1 200
5 7
1 5
2 4
3 5
1 3
2 4
3 2
2 5
3 4 200
0 0
```

output:

Code: Select all

```
Yes, Teobaldo can travel.
Yes, Teobaldo can travel.
```