How to solve spoj problem ADAZOO

Revision en2, by shoya, 2018-11-04 22:25:57

Problem link

Here is my approach :
- Calculate All pairs shortest distance using floyd Warshall for every pair of cell.
- Then dp[subset] = optimal answer for this subset.
- For each tyger u subset try to connect that with this subset in minimal way using pre-calculated shortest distances such that dp[subset u] = dp[subset] + min_dis.
- At last take sum for all subsets.

But this gives wrong answer. Please help.
Can someone tell me the approach to solve this problem ?

Tags #spoj, #adazoo

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English shoya 2018-11-04 22:25:57 62
en1 English shoya 2018-11-02 22:55:01 667 Initial revision (published)