10171 - Meeting Prof. Miguel...

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

aloha
New poster
Posts: 3
Joined: Mon Feb 04, 2002 2:00 am

10171 - Meeting Prof. Miguel...

Post by aloha » 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.

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

Post by shahriar_manzoor » Tue Feb 05, 2002 3:51 am

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

aloha
New poster
Posts: 3
Joined: Mon Feb 04, 2002 2:00 am

Post by aloha » 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?

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

Post by shahriar_manzoor » 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.

aloha
New poster
Posts: 3
Joined: Mon Feb 04, 2002 2:00 am

Post by aloha » Tue Feb 05, 2002 11:27 am

No. It's correct.

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

Post by shahriar_manzoor » Tue Feb 05, 2002 4:24 pm

Send me your code at shahriar@neksus.com

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » 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
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)

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

10171 WA

Post by Chow Wai Chung » 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]
Last edited by Chow Wai Chung on Mon Jun 23, 2003 3:26 am, edited 1 time in total.

Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:

Post by Lamas » 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.
good algorithm is important~

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

Post by Chow Wai Chung » 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 :oops:

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

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

Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:

Post by Lamas » Fri Jun 27, 2003 8:57 am

I got accepted!! :D

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~

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

Post by Chow Wai Chung » 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.

Lamas
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:

Post by Lamas » Sun Jun 29, 2003 6:15 am

I am not crazy, but very crazy.... 8)

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~

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

Post by Chow Wai Chung » Sun Jun 29, 2003 3:41 pm

:lol: :lol: :lol: :lol: :lol:

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 :wink:

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » 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
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)

Post Reply

Return to “Volume 101 (10100-10199)”