Page 1 of 3

Posted: Sun Dec 23, 2001 12:00 pm
by junjieliang
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
by junjieliang
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
by wyvmak
which part is it incorrect? i get WA too

Posted: Thu Dec 27, 2001 7:52 am
by junjieliang
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
by wyvmak
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'?

Posted: Mon Dec 31, 2001 5:54 am
by junjieliang
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.

558

Posted: Tue May 06, 2003 5:59 pm
by j0rdi
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]

558

Posted: Tue Sep 23, 2003 6:58 am
by jai166
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! :D But I am really confused about why the answer is correct! :o 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? :D I am really confused!! :o
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]

Posted: Thu Nov 24, 2005 1:38 pm
by Mg9H
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 ;)

Posted: Tue Nov 29, 2005 5:03 pm
by roticv
It's bellman-ford, not ford-bellman :D

Posted: Fri Mar 03, 2006 5:04 pm
by Ming Han
What algorithm is recommended?
Bellman-Ford or Floyd Warshall?

Posted: Sun Jun 04, 2006 8:56 pm
by jan_holmes
I think Bellman Ford Algorithm suits well in this problem... :D

Posted: Wed May 02, 2007 4:11 pm
by sjn
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: Wed May 02, 2007 7:35 pm
by Jan
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?
So, there are values in the judge input for which your calculation result is greater than 2000000.

Posted: Thu May 03, 2007 4:35 am
by sjn
Jan wrote:
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?
So, there are values in the judge input for which your calculation result is greater than 2000000.
But the thing is that
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? :-? :-? :-?