I modified my bfs() and got it AC in 0.04 seconds.
Can someone give some detail about this recurrence relation. I think most of the people used Larry's method.Larry wrote: Use dynamic programming by first finding a recurrence..
Moderator: Board moderators
Code: Select all
3 2
1 2
2 3
2 2 0
Code: Select all
Yes, Teobaldo can travel.
Code: Select all
code removed
Code: Select all
2 1
1 2
1 2 4
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: Select all
removed after AC
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
Code: Select all
Yes, Teobaldo can travel.
Yes, Teobaldo can travel.