10171 - Meeting Prof. Miguel...

[aloha]

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.

[shahriar_manzoor]

Paths with zero cost are there! It's a magical city

[aloha]

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?

[shahriar_manzoor]

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.

[aloha]

No. It's correct.

[shahriar_manzoor]

Send me your code at shahriar@neksus.com

[Dominik Michniewski]

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

[Chow Wai Chung]

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]

[Lamas]

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.

[Chow Wai Chung]

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?

[Lamas]

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!

[Chow Wai Chung]

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.

[Lamas]

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~~

[Chow Wai Chung]

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

[Dominik Michniewski]

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