10803 - Thunder Mountain
Moderator: Board moderators
10803 - Thunder Mountain
I used this algorithm but i get WA:
1.For each pair of nodes i calculate the distance, if it is less or equal than 10 then d[j] = d[j] = that distance else d[j] = d[j] = infinity.
2.Apply Floyd to find All Pairs Shortest Paths.
3.Then i look for the maximum distance.
What is wrong...???
Thanx in advance,
Yandry.
1.For each pair of nodes i calculate the distance, if it is less or equal than 10 then d[j] = d[j] = that distance else d[j] = d[j] = infinity.
2.Apply Floyd to find All Pairs Shortest Paths.
3.Then i look for the maximum distance.
What is wrong...???
Thanx in advance,
Yandry.
I am also getting WA, this is my code.
Code: Select all
Cut after AC...
Last edited by neno_uci on Wed Mar 09, 2005 9:29 am, edited 1 time in total.
- Abednego
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
- Contact:
Your dis variable is of type "real". So when you compare it to 100 using the <= operator, things will break if dis=100.0000001. I couldn't find any other mistakes on first glance. I've never used pascal, and I don't have a pascal compiler. Otherwise, I could try running your solution on the official input data to see where the mistake is.
If only I had as much free time as I did in college...
hmmmm... am i missing something?
1. connects all which d<=100 (long)
2. sqrt the distance for them
3. floyd it
4. if its not connected, send kurdy
5. if it is, check for the biggest distance
6. round it, print it
1. connects all which d<=100 (long)
2. sqrt the distance for them
3. floyd it
4. if its not connected, send kurdy
5. if it is, check for the biggest distance
6. round it, print it
Code: Select all
...
Last edited by technobug on Thu Jan 13, 2005 10:35 pm, edited 1 time in total.
Technobug: When using Floyd-Warshall, the order in which you nest the cycles matters. Yours is wrong. The k-cycle must be the outermost one.
Note that in the correct implementation, after running the k-cycle x times the value in d[p][q] is the shortest p-q path such that all intermediate vertices have numbers not exceeding x. (This is how the algorithm works )
Also, if you initialize d[j] to a sufficiently large value for i!=j, you may omit the con[][] array from your solution completely. Not that this matters but the presence of the con[][] array makes your implementation unnecesarilly complicated.
Note that in the correct implementation, after running the k-cycle x times the value in d[p][q] is the shortest p-q path such that all intermediate vertices have numbers not exceeding x. (This is how the algorithm works )
Also, if you initialize d[j] to a sufficiently large value for i!=j, you may omit the con[][] array from your solution completely. Not that this matters but the presence of the con[][] array makes your implementation unnecesarilly complicated.
hmmm..... something seemed wrong... thanks misof...
btw, i got everything you sugested, even took out the con array (which i am always afraid, as i usually mess things up)....
the resulting code is much more simple but still did not get it right:
hmmm.... 10000.0 solved the problem thanks sir....
btw, i got everything you sugested, even took out the con array (which i am always afraid, as i usually mess things up)....
the resulting code is much more simple but still did not get it right:
Code: Select all
....
Last edited by technobug on Thu Jan 13, 2005 11:34 pm, edited 1 time in total.
Hello.
I'm getting this problem WA.Somebody give me some tests please.
Thanks.
I'm getting this problem WA.Somebody give me some tests please.
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650