shoya's blog

By shoya, history, 5 years ago, In English

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 ?

  • Vote: I like it
  • -5
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Have you considered that shortest paths may overlap at some squares? If they do then you will computing the cost to connect squares more than once in your final answer. For example if the min cost to connect Tyger 1 with Tyger 2 consists of connecting some square X to another square Y, which is also part of the min cost path to connect Tyger 2 with 3, then when you expand your set from 1, 2 to 1, 2, 3 via connecting 2 to 3 you will count the cost of connecting X to Y twice.