Page 1 of 5

10171 - Meeting Prof. Miguel...

Posted: Mon Feb 04, 2002 8:10 pm
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.

Posted: Tue Feb 05, 2002 3:51 am
Paths with zero cost are there! It's a magical city

Posted: Tue Feb 05, 2002 8:56 am
Thanks.

But I do make up some test cases with 0 costs. Seems to be working fine. Can you suggest some special cases for me to test?

Posted: Tue Feb 05, 2002 10:18 am
There may also be self loops. For example if I and prof.miguel are both on the same city and there is a self loop, we can meet in zero cost. But your program may show the cost of the self loop.

Posted: Tue Feb 05, 2002 11:27 am
No. It's correct.

Posted: Tue Feb 05, 2002 4:24 pm
Send me your code at shahriar@neksus.com

Posted: Mon Apr 28, 2003 1:27 pm
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

10171 WA

Posted: Mon Jun 16, 2003 2:37 am
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]

Posted: Sun Jun 22, 2003 5:33 pm
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:

Code: Select all

`````` if(me==prof)
printf("0\n");
``````
It should be

Code: Select all

`````` if(me==prof)
printf("0 %c\n",me);
``````
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.

Posted: Mon Jun 23, 2003 3:14 am
I still cannot believe that i made a such stupid mistake when two person on the same place

But after i correct it, i still got WA!!!!!!

For your second point, i don't know what is your meaning, can you explain more?

Posted: Fri Jun 27, 2003 8:57 am
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!

Posted: Fri Jun 27, 2003 3:47 pm
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??
The 'min' you have found may not be the real minmum. if you count it together with the real one, it is wrong!
Please tell me clearly, i also want AC.

Posted: Sun Jun 29, 2003 6:15 am
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~~

Posted: Sun Jun 29, 2003 3:41 pm

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

Posted: Mon Jun 30, 2003 12:02 pm
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