558 - Wormholes

[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?

[junjieliang]

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

[wyvmak]

which part is it incorrect? i get WA too

[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.

[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'?

[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.

[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]

[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! 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]

[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

[roticv]

It's bellman-ford, not ford-bellman

[Ming Han]

What algorithm is recommended?
Bellman-Ford or Floyd Warshall?

[jan_holmes]

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

[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?

[Jan]

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.

[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?

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?