558 - Wormholes
Moderator: Board moderators
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
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.
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
558
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=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
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[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]
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
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
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?
Ami ekhono shopno dekhi...
HomePage
HomePage
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?