10793 - The Orc Attack

[harry]

Hi every body.

this problem seems to be easy.
what i have done is
1. i used floyd warshall for shortest distance
2. then check whether any point exist which is equidistance from 1,2,3,4,5
(the fr five points)
3.if such point exists then did what the problem said.

sorry for paosting the code.
but i have got w.a. for 15 times.tried with all possible ways.
plz help

Code: Select all

got ac

[Eduard]

Code: Select all

There may be multiple occurrences of the same U, V pair in the input - it is up to you to decide which one to use

Which one have You used???

[harry]

the shortest one.


if(G[s][e]>cost)
{
G[s][e]=cost;
G[e][s]=cost;
}
hope i am right

[krijger]

Your floyd-warshall is incorrect. The 'intermediate' node should be in the outer loop.

[shamim]

Another issue, although not important,

what is the need for this:
[cpp]
if(s>e)
{
i=s;
s=e;
e=i;
}
[/cpp]

[harry]

thanks a lot.really a silly mistake.thanks onece again.

[TISARKER]

I read the problem again and again.
But I don't understand How the node 7 has a cost of 51 where I think
node has a cost of 52 as the farthest point.
If I wrong , Please show me the path where node 7 has a cost of 51.

[kmhasan]

Try 7-8-4-6-10. The cost would be 2+10+4+35=51.

[TISARKER]

Thank u Boss.Actually I am a dull student.
So for this, I couldnot solve this probem in the NCPC2004.
But as a Programmer, I should catch this problem.
Ok Thanks.
May Allah make u as a more good PS in future.

**** PS means "Problem Setter" not "Private Secretary"

[technobug]

Hey people, I am trying the same idea as his (simple floyd warshall then look for the best vertex) but gets WA... tried a few test cases which I tried to find my problem but did not work out.

The algo is basically the same as his (therefore I did not specify it that much, there are a few comments though)

[cpp]
ABCDE
[/cpp]

Any ideas?

[Cho]

hi, technobug, your code fails on this input:

Code: Select all

1
7 5
1 6 1
2 6 1
3 6 1
4 6 1
5 6 1

The correct output should be "Map 1: -1".

[Eduard]

I'm getting this problem WA.Please someone give me some tests.
Thanks.

[unknown_error]

Edward,

this is a simple problem and no special case is there. do exactly according to description. first found the rally point(s). for each point find the max distance to all nodes fron the rally node. ( search from 1 to n node. take the max value. suppose there 10 nodes and the rally node is 7. suppose 7 is connected to all nodes except node 9. then the max value will be infinity. otherwise the max of all nodes ). if u got several such rally nodes take the minimal max value of the rally points.

if there are any isolated node then output is -1. ( unfortunately i overlook this part and got WA in the contest. )
else if there is no rally point then output is -1
else output according to description.

if u also fails afterall, try to recode it or check I/O, initiaization or you floyed-warshall code.

[Larry]

Code: Select all

      FOR(j,n) { 
         if(con[i][j] && dmax<mat[i][j]) dmax = mat[i][j]; 
      } 

The rally point has to be connected to every other point..

[technobug]

Code: Select all

      FOR(j,n) { 
         if(con[i][j] && dmax<mat[i][j]) dmax = mat[i][j]; 
      } 

The rally point has to be connected to every other point..

Thanks Cho, Larry....
So I added something:

Code: Select all

      FOR(j,n) { 
         // skip it if not connected
         if(i!=j && !con[i][j]) goto f;
         if(con[i][j] && dmax<mat[i][j]) dmax = mat[i][j]; 
      } 

It corrected the sample input from Cho but did not gimme acc... looks like I did what unknown_error said, I will check it again later today...