## 10171 - Meeting Prof. Miguel...

Moderator: Board moderators

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

### 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.

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am
Paths with zero cost are there! It's a magical city

aloha
New poster
Posts: 3
Joined: Mon Feb 04, 2002 2:00 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
Posts: 399
Joined: Sat Jan 12, 2002 2:00 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
No. It's correct.

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am
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:
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

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:
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
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
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:
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!
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
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:
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~~
good algorithm is important~

Chow Wai Chung
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

Dominik Michniewski
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
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)