10171  Meeting Prof. Miguel...
Moderator: Board moderators
10171  Meeting Prof. Miguel...
Hi,
I use twice dijkstra to solve the problem. I think I solved it but the judge replies WA. It seems to be a very simple problem that would hardly go wrong. Is there any special case to consider?
Thanks.
I use twice dijkstra to solve the problem. I think I solved it but the judge replies WA. It seems to be a very simple problem that would hardly go wrong. Is there any special case to consider?
Thanks.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Send me your code at shahriar@neksus.com

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Could anyone help me with this problem ?
I use Dijkstra to find cost for both people. I think, that my program works fine with paths of 0 costs, and in situations , in which both are in one place, and so on.
Best regards
DM
I use Dijkstra to find cost for both people. I think, that my program works fine with paths of 0 costs, and in situations , in which both are in one place, and so on.
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 New poster
 Posts: 21
 Joined: Sun Jan 19, 2003 4:01 pm
 Location: Hong Kong
10171 WA
I use Dijkstra twice to find the cost, then find the mininal cost.
In my test cases, i had put some paths with zero cost and zero self loop, and my program seems correct on this.
Can anyone point out what are the special cases i missed??
[cpp]
#include <stdio.h>
int main()
{
int young[26][26],more[26][26],y_length[26],m_length[26],N,tmp,min;
char people,dir,a,b,count,me,prof,meet[26];
bool yfound[26],mfound[26],found,y_connect[26][26],m_connect[26][26];
scanf("%d",&N);
while(N!=0)
{
getchar();
for(a=0;a<26;a++)
{
y_length[a]=100000;
m_length[a]=100000;
yfound[a]=false;
mfound[a]=false;
for(b=0;b<26;b++)
{
y_connect[a]=false;
m_connect[a]=false;
}
}
while(N>0)
{
scanf("%c %c %c %c %d",&people,&dir,&a,&b,&tmp);
getchar();
if(people=='Y')
{
young[a'A'][b'A']=tmp;
y_connect[a'A'][b'A']=true;
if(dir=='B')
{
young[b'A'][a'A']=tmp;
y_connect[b'A'][a'A']=true;
}
}
else
{
more[a'A'][b'A']=tmp;
m_connect[a'A'][b'A']=true;
if(dir=='B')
{
more[b'A'][a'A']=tmp;
m_connect[b'A'][a'A']=true;
}
}
}
scanf("%c %c",&me,&prof);
getchar();
if(me==prof)
printf("0 %c\n",me);
else
{
y_length[me'A']=0;
m_length[prof'A']=0;
// use twice dijkstra to count the S.P.
count=0;
while(count<26)
{
min=1000000;
for(a=0;a<26;a++)
if(!yfound[a] && y_length[a]<min )
{
min=y_length[a];
b=a;
}
if(y_length!=100000)
{
yfound=true;
for(a=0;a<26;a++)
if(y_connect[a]&&!yfound[a])
if(y_length[a]>y_length+young[a])
y_length[a]=y_length+young[a];
count++;
}
else
break;
}
count=0;
while(count<26)
{
min=10000000;
for(a=0;a<26;a++)
if(!mfound[a] && m_length[a]<min)
{
min=m_length[a];
b=a;
}
if(m_length!=100000)
{
mfound[b]=true;
for(a=0;a<26;a++)
if(m_connect[b][a]&&!mfound[a])
if(m_length[a]>m_length[b]+more[b][a])
m_length[a]=m_length[b]+more[b][a];
count++;
}
else
break;
}
// find the minimum cost meeting place
found=false;
min=100000;
for(a=0;a<26;a++)
if(yfound[a]&&mfound[a])
if(y_length[a]+m_length[a]<min)
{
found=true;
min=y_length[a]+m_length[a];
meet[count=0]=a;
}
else if(y_length[a]+m_length[a]==min)
meet[++count]=a;
if(found)
{
printf("%d",min);
for(a=0;a<=count;a++)
printf(" %c",meet[a]+'A');
printf("\n");
}
else
printf("You will never meet.\n");
}
scanf("%d",&N);
}
return 0;
}
[/cpp]
In my test cases, i had put some paths with zero cost and zero self loop, and my program seems correct on this.
Can anyone point out what are the special cases i missed??
[cpp]
#include <stdio.h>
int main()
{
int young[26][26],more[26][26],y_length[26],m_length[26],N,tmp,min;
char people,dir,a,b,count,me,prof,meet[26];
bool yfound[26],mfound[26],found,y_connect[26][26],m_connect[26][26];
scanf("%d",&N);
while(N!=0)
{
getchar();
for(a=0;a<26;a++)
{
y_length[a]=100000;
m_length[a]=100000;
yfound[a]=false;
mfound[a]=false;
for(b=0;b<26;b++)
{
y_connect[a]=false;
m_connect[a]=false;
}
}
while(N>0)
{
scanf("%c %c %c %c %d",&people,&dir,&a,&b,&tmp);
getchar();
if(people=='Y')
{
young[a'A'][b'A']=tmp;
y_connect[a'A'][b'A']=true;
if(dir=='B')
{
young[b'A'][a'A']=tmp;
y_connect[b'A'][a'A']=true;
}
}
else
{
more[a'A'][b'A']=tmp;
m_connect[a'A'][b'A']=true;
if(dir=='B')
{
more[b'A'][a'A']=tmp;
m_connect[b'A'][a'A']=true;
}
}
}
scanf("%c %c",&me,&prof);
getchar();
if(me==prof)
printf("0 %c\n",me);
else
{
y_length[me'A']=0;
m_length[prof'A']=0;
// use twice dijkstra to count the S.P.
count=0;
while(count<26)
{
min=1000000;
for(a=0;a<26;a++)
if(!yfound[a] && y_length[a]<min )
{
min=y_length[a];
b=a;
}
if(y_length!=100000)
{
yfound=true;
for(a=0;a<26;a++)
if(y_connect[a]&&!yfound[a])
if(y_length[a]>y_length+young[a])
y_length[a]=y_length+young[a];
count++;
}
else
break;
}
count=0;
while(count<26)
{
min=10000000;
for(a=0;a<26;a++)
if(!mfound[a] && m_length[a]<min)
{
min=m_length[a];
b=a;
}
if(m_length!=100000)
{
mfound[b]=true;
for(a=0;a<26;a++)
if(m_connect[b][a]&&!mfound[a])
if(m_length[a]>m_length[b]+more[b][a])
m_length[a]=m_length[b]+more[b][a];
count++;
}
else
break;
}
// find the minimum cost meeting place
found=false;
min=100000;
for(a=0;a<26;a++)
if(yfound[a]&&mfound[a])
if(y_length[a]+m_length[a]<min)
{
found=true;
min=y_length[a]+m_length[a];
meet[count=0]=a;
}
else if(y_length[a]+m_length[a]==min)
meet[++count]=a;
if(found)
{
printf("%d",min);
for(a=0;a<=count;a++)
printf(" %c",meet[a]+'A');
printf("\n");
}
else
printf("You will never meet.\n");
}
scanf("%d",&N);
}
return 0;
}
[/cpp]
Last edited by Chow Wai Chung on Mon Jun 23, 2003 3:26 am, edited 1 time in total.
Hello, first time to reply you here. I just want more people to reply, as I got WA too.
However, I found some error in your code.
First. what you have print out when:
It should be
Second, I am not sure am I right( I got wrong answer too). please read carefully the question and the output require.
It says " Print the minimum energy cost and the place, which is most suitable for us to meet. If there is more than one place to meet print all of them in order in the same line."
So you should print the place with the minimum energy first before other place they can meet.
However, I found some error in your code.
First. what you have print out when:
Code: Select all
if(me==prof)
printf("0\n");
Code: Select all
if(me==prof)
printf("0 %c\n",me);
It says " Print the minimum energy cost and the place, which is most suitable for us to meet. If there is more than one place to meet print all of them in order in the same line."
So you should print the place with the minimum energy first before other place they can meet.
good algorithm is important~

 New poster
 Posts: 21
 Joined: Sun Jan 19, 2003 4:01 pm
 Location: Hong Kong
I got accepted!!
try this:
6
Y U A Z 0
Y U C A 0
Y U A Y 0
M U D Z 0
M B C D 0
M B C Y 0
A D
0 Y Z
Besides, there may have problem too.
[cpp]
close!!
[/cpp]
The 'min' you have found may not be the real minmum. if you count it together with the real one, it is wrong!
try this:
6
Y U A Z 0
Y U C A 0
Y U A Y 0
M U D Z 0
M B C D 0
M B C Y 0
A D
0 Y Z
Besides, there may have problem too.
[cpp]
close!!
[/cpp]
The 'min' you have found may not be the real minmum. if you count it together with the real one, it is wrong!
Last edited by Lamas on Sun Jun 29, 2003 6:39 am, edited 1 time in total.
good algorithm is important~

 New poster
 Posts: 21
 Joined: Sun Jan 19, 2003 4:01 pm
 Location: Hong Kong
For your data, i have the same output with you. What is the problem?
Also, why did you say my program may have the problem on finding the minimum value??
Also, why did you say my program may have the problem on finding the minimum value??
Please tell me clearly, i also want AC.The 'min' you have found may not be the real minmum. if you count it together with the real one, it is wrong!
I am not crazy, but very crazy....
You,
[cpp]
if(me==prof) printf("0 %c\n",me);
else {
:
}
[/cpp]
So, I gress you will have error when more then one point take 0 energy. If you are right with the test case, I think you are ok.
I think you are right about the second problem. I misunderstand the code.
PS. How can you do 108 ans 10000 so quick. teach me~~
You,
[cpp]
if(me==prof) printf("0 %c\n",me);
else {
:
}
[/cpp]
So, I gress you will have error when more then one point take 0 energy. If you are right with the test case, I think you are ok.
I think you are right about the second problem. I misunderstand the code.
PS. How can you do 108 ans 10000 so quick. teach me~~
good algorithm is important~

 New poster
 Posts: 21
 Joined: Sun Jan 19, 2003 4:01 pm
 Location: Hong Kong
I got AC now!!!! Thank you for your tips, my program have a bug on this test case:
2
Y U B D 0
M U B D 0
B B
the correct output should be:
0 B D
but i got this:
0 B
Thank you very much
ps. 108 and 10000 is offtopic in this volume, but i found you had already solved them, what do you what to ask me?? please send email to me or ask in volume 1 or C

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Could anyone help me and post me some special cases for this problem? I've got correct answers for all inputs which I found, but I got WA from OJ. I use Dijkstra twice to find minimal cost paths in graph ....
Best regards
DM
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)