Posted:

**Sun Dec 23, 2001 12:00 pm**Is there any tricks in this problem? I keep on getting "Memory limit exceeded", but I have checked my array time and again and found no problem! Is there any other reason for memory limit exceeded?

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

Posted: **Sun Dec 23, 2001 12:00 pm**

Is there any tricks in this problem? I keep on getting "Memory limit exceeded", but I have checked my array time and again and found no problem! Is there any other reason for memory limit exceeded?

Posted: **Mon Dec 24, 2001 5:48 am**

Nvm, I solved the problem using pointers... but that also means that the problem description is not correct...

Posted: **Wed Dec 26, 2001 8:33 am**

which part is it incorrect? i get WA too

Posted: **Thu Dec 27, 2001 7:52 am**

I think the limits for the number of wormholes or star systems are wrong, because when I used arrays, I got "Memory Limit Exceeded". However, when I turned to malloc, I got accepted. That should be all the problems that I faced. If you still don't get accepted, maybe you could reply to this thread and I will see how I can help you.

Posted: **Sat Dec 29, 2001 11:06 am**

thanks for your help.

i think the input is 1<=n<=1000, and 0<=m<=2000. anyway, one question is,

is that you have to find a loop <0 that must be started with system 0? or any loop will output 'possible'?

i think the input is 1<=n<=1000, and 0<=m<=2000. anyway, one question is,

is that you have to find a loop <0 that must be started with system 0? or any loop will output 'possible'?

Posted: **Mon Dec 31, 2001 5:54 am**

The loop wil have to start at 0, but the loop does not have to include 0. Eg:

1

4 4

0 1 10

1 2 20

2 3 30

3 1 -1000

Here the loop is from 1 2 3 1 2 3..., but 0 is the starting point.

1

4 4

0 1 10

1 2 20

2 3 30

3 1 -1000

Here the loop is from 1 2 3 1 2 3..., but 0 is the starting point.

Posted: **Tue May 06, 2003 5:59 pm**

I get all times Wrong Answer(WA), but i can't find where is the error. Someone can help me.

Here is my code in C.

[c]#include <stdio.h>

struct nodo

{

int val;

int dist;

struct nodo *sig;

};

struct nodo *a[1000], *z;

int aa[1000];

void inicializar(int n_stars,int n_worm)

{

int i;

int x,y,d;

char line[80];

struct nodo *t;

z=(struct nodo *)malloc(sizeof(struct nodo));

z->sig=z;

for(i=0; i<n_stars;i++)

{

aa*=0;*

}

for(i=0; i<n_stars;i++)

{

a*=z;*

}

for (i=0; i<n_worm; i++)

{

gets(line);

sscanf(line,"%d %d %d",&x,&y,&d);

t=(struct nodo *)malloc(sizeof(struct nodo));

aa[y]=1;

t->val=y; t->dist=d; t->sig=a[x]; a[x]=t;

}

}

int find_cycle(int n_stars)

{

int i=0;

int j=0;

int find=0;

while(i<n_stars && find!=1)

{

if(aa*==1)*

{

find=tract_starsyst(a*,i,0);*

for(j=0;j<n_stars;j++)

{

if (aa[j]==2)

{

aa[j]=1;

}

}

}

i++;

}

return(find);

}

int tract_starsyst(struct nodo *t,int orig, int time)

{

int temps;

int trobat=0;

int j;

struct nodo *aux;

temps=time;

aux=t;

while (aux!=z && aa[aux->val]!=2 && trobat!=1)

{

aa[aux->val]=2;

if (aux->val==orig)

{

temps=temps+aux->dist;

if(temps<0)

{

trobat=1;

}

}

else

{

temps=temps+aux->dist;

trobat=tract_starsyst(a[aux->val],orig,temps);

}

aux=aux->sig;

}

return(trobat);

}

main (int argc,char *arv[])

{

int indx=0;

int i;

char line[80];

int n_cases;

int n_stars_system=0;

int n_wormholes=0;

int possible=0;

gets(line);

sscanf(line,"%d",&n_cases);

for(i=0;i<n_cases;i++)

{

gets(line);

sscanf(line,"%d %d",&n_stars_system,&n_wormholes);

inicializar(n_stars_system,n_wormholes);

if (find_cycle(n_stars_system)==1)

{

printf("possible\n");

}

else

{

printf("not possible\n");

}

}

}[/c]

Here is my code in C.

[c]#include <stdio.h>

struct nodo

{

int val;

int dist;

struct nodo *sig;

};

struct nodo *a[1000], *z;

int aa[1000];

void inicializar(int n_stars,int n_worm)

{

int i;

int x,y,d;

char line[80];

struct nodo *t;

z=(struct nodo *)malloc(sizeof(struct nodo));

z->sig=z;

for(i=0; i<n_stars;i++)

{

aa

}

for(i=0; i<n_stars;i++)

{

a

}

for (i=0; i<n_worm; i++)

{

gets(line);

sscanf(line,"%d %d %d",&x,&y,&d);

t=(struct nodo *)malloc(sizeof(struct nodo));

aa[y]=1;

t->val=y; t->dist=d; t->sig=a[x]; a[x]=t;

}

}

int find_cycle(int n_stars)

{

int i=0;

int j=0;

int find=0;

while(i<n_stars && find!=1)

{

if(aa

{

find=tract_starsyst(a

for(j=0;j<n_stars;j++)

{

if (aa[j]==2)

{

aa[j]=1;

}

}

}

i++;

}

return(find);

}

int tract_starsyst(struct nodo *t,int orig, int time)

{

int temps;

int trobat=0;

int j;

struct nodo *aux;

temps=time;

aux=t;

while (aux!=z && aa[aux->val]!=2 && trobat!=1)

{

aa[aux->val]=2;

if (aux->val==orig)

{

temps=temps+aux->dist;

if(temps<0)

{

trobat=1;

}

}

else

{

temps=temps+aux->dist;

trobat=tract_starsyst(a[aux->val],orig,temps);

}

aux=aux->sig;

}

return(trobat);

}

main (int argc,char *arv[])

{

int indx=0;

int i;

char line[80];

int n_cases;

int n_stars_system=0;

int n_wormholes=0;

int possible=0;

gets(line);

sscanf(line,"%d",&n_cases);

for(i=0;i<n_cases;i++)

{

gets(line);

sscanf(line,"%d %d",&n_stars_system,&n_wormholes);

inicializar(n_stars_system,n_wormholes);

if (find_cycle(n_stars_system)==1)

{

printf("possible\n");

}

else

{

printf("not possible\n");

}

}

}[/c]

Posted: **Tue Sep 23, 2003 6:58 am**

The following is the way I count the path......

[c]/*for(k=0;k<maxwarm-1;k++)*/

for(i=0;i<maxstar;i++)/* Step */

for(j=0;j<maxstar;j++)/* End */

if(len[0][j]>len[0]*+len**[j])*

len[0][j]=len[0]*+len**[j];[/c]*

Actually, I**Accepted**! But I am really confused about why the answer is correct! In my opinion, this loop should be done by **N-2** times.

After that, I check if there is negative path......

[c] for(pass=1,i=0;i<maxstar&&pass;i++)/* Step */

for(j=0;j<maxstar&&pass;j++)/* End */

if(len[0][j]>len[0]*+len**[j])pass=0;[/c]*

Could you do me a favor? I am really confused!!

The following is my source code:

[c]/* 558 Wormholes */

#include<stdio.h>

#define MAX 1000

#define MAXNUM 10000000

int len[MAX][MAX];

void main(void)

{

int i,j,k,maxstar,maxwarm,x,y,t;

unsigned int alltimes;

unsigned char pass;

scanf("%ld",&alltimes);

while( alltimes ){

alltimes--;

scanf("%d%d",&maxstar,&maxwarm);

/* Set First Value - MAXNUM */

for(i=0;i<maxstar;i++)

for(j=0;j<maxstar;j++)

len*[j]=MAXNUM;*

/* Input */

for(i=0;i<maxwarm;i++){

scanf("%d%d%d",&x,&y,&t);

len[x][y]=t;

}

/*for(k=0;k<maxwarm-1;k++)*/

for(i=0;i<maxstar;i++)/* Step */

for(j=0;j<maxstar;j++)/* End */

if(len[0][j]>len[0]*+len**[j])*

len[0][j]=len[0]*+len[i][j];*

for(pass=1,i=0;i<maxstar&&pass;i++)/* Step */

for(j=0;j<maxstar&&pass;j++)/* End */

if(len[0][j]>len[0][i]+len[i][j])pass=0;

if(pass)puts("not possible");

else puts("possible");

}

}[/c]

[c]/*for(k=0;k<maxwarm-1;k++)*/

for(i=0;i<maxstar;i++)/* Step */

for(j=0;j<maxstar;j++)/* End */

if(len[0][j]>len[0]

len[0][j]=len[0]

Actually, I

After that, I check if there is negative path......

[c] for(pass=1,i=0;i<maxstar&&pass;i++)/* Step */

for(j=0;j<maxstar&&pass;j++)/* End */

if(len[0][j]>len[0]

Could you do me a favor? I am really confused!!

The following is my source code:

[c]/* 558 Wormholes */

#include<stdio.h>

#define MAX 1000

#define MAXNUM 10000000

int len[MAX][MAX];

void main(void)

{

int i,j,k,maxstar,maxwarm,x,y,t;

unsigned int alltimes;

unsigned char pass;

scanf("%ld",&alltimes);

while( alltimes ){

alltimes--;

scanf("%d%d",&maxstar,&maxwarm);

/* Set First Value - MAXNUM */

for(i=0;i<maxstar;i++)

for(j=0;j<maxstar;j++)

len

/* Input */

for(i=0;i<maxwarm;i++){

scanf("%d%d%d",&x,&y,&t);

len[x][y]=t;

}

/*for(k=0;k<maxwarm-1;k++)*/

for(i=0;i<maxstar;i++)/* Step */

for(j=0;j<maxstar;j++)/* End */

if(len[0][j]>len[0]

len[0][j]=len[0]

for(pass=1,i=0;i<maxstar&&pass;i++)/* Step */

for(j=0;j<maxstar&&pass;j++)/* End */

if(len[0][j]>len[0][i]+len[i][j])pass=0;

if(pass)puts("not possible");

else puts("possible");

}

}[/c]

Posted: **Thu Nov 24, 2005 1:38 pm**

It's a little late for replying this but your algorithm works correctly because

the first loop is a Ford-Bellman loop, which works perfectly in graph with negative edges but no negative cycle.

Since Ford-Bellman algorithm broke when graphs have negative cycle (by "broke", i mean the minimum distance can still be decreased), the second loop repeat Ford-Bellman again to see if it broke or not. If it did, there's at least 1 negative cycle in some path from 0 to some node, which means the answer is "possible".

Thank you very much for posting this question, i cannot solve this one within the time-limit and your code made me recall this interesting property of Ford-Bellman

the first loop is a Ford-Bellman loop, which works perfectly in graph with negative edges but no negative cycle.

Since Ford-Bellman algorithm broke when graphs have negative cycle (by "broke", i mean the minimum distance can still be decreased), the second loop repeat Ford-Bellman again to see if it broke or not. If it did, there's at least 1 negative cycle in some path from 0 to some node, which means the answer is "possible".

Thank you very much for posting this question, i cannot solve this one within the time-limit and your code made me recall this interesting property of Ford-Bellman

Posted: **Tue Nov 29, 2005 5:03 pm**

It's bellman-ford, not ford-bellman

Posted: **Fri Mar 03, 2006 5:04 pm**

What algorithm is recommended?

Bellman-Ford or Floyd Warshall?

Bellman-Ford or Floyd Warshall?

Posted: **Sun Jun 04, 2006 8:56 pm**

I think Bellman Ford Algorithm suits well in this problem...

Posted: **Wed May 02, 2007 4:11 pm**

what's wrong with the judge?

when i set INFINITY as "20000000" and got AC

when i set INFINITY as "2000000" and got WA

any suggestion?

when i set INFINITY as "20000000" and got AC

when i set INFINITY as "2000000" and got WA

any suggestion?

Posted: **Wed May 02, 2007 7:35 pm**

So, there are values in the judge input for which your calculation result is greater than 2000000.sjn wrote:what's wrong with the judge?

when i set INFINITY as "20000000" and got AC

when i set INFINITY as "2000000" and got WA

any suggestion?

Posted: **Thu May 03, 2007 4:35 am**

But the thing is thatJan wrote:So, there are values in the judge input for which your calculation result is greater than 2000000.sjn wrote:what's wrong with the judge?

when i set INFINITY as "20000000" and got AC

when i set INFINITY as "2000000" and got WA

any suggestion?

1: the description of input says the value of t (time) is between -1000 and 1000;

2: when i set INFINITY as "20000" and got AC

strange?