raj_meena's blog

WA on SPOJ TOURS
By raj_meena, history, 9 years ago, In English

http://www.spoj.com/problems/TOURS/ Above is problem link. My approach is follow :

1. Find All Pairs Shortest paths
2. Create Flow Network where flow will be 1 and cost will be distance from i to j.
3. Add Super Source and Super Sink then Using mincostmaxflow find minimum cost print it.

Any Hint?? , Test case, your approach anything all are welcome :D :)

Sorry for my poor english

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

»
9 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

What kind of flow network are you creating?

If you build a bipartite graph and perform min-cost max-flow, it will give you the minimum cost to match nodes. Additionally, each node will have in-degree 1 and out-degree 1, so it will be cyclical.

A regular graph won't work.

Also, you just have to add edges as given in the input. There's no need to find all pairs shortest paths. In fact, if you add edges based on shortest paths, it will surely give you WA, because some places will be visited more than once.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey yes i was creating bipartite graph and also flow will be 1 for each vertex from super source and also in super sink. and thank you so much tenshi_kanade i got AC just remove flyod warshall from code. :D :) i didn't notice that using shortest path vertexes can be occur multiple times :D .

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

probably the 1000th blog regarding TOURS problem

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey Can you give me link of some blogs regarding TOURS problem

    → Reply