title: Why am I keep getting WA for this solution for SPOJ FISHER?
body: <p>I am trying to solve this problem, I think I have come up with a correct answer, but I am keep getting WA (wrong answer) response from the judge.</p>
  
  <p><a href="http://www.spoj.com/problems/FISHER/" rel="nofollow">http://www.spoj.com/problems/FISHER/</a></p>
  
  <p>The problem distilled, is, given a complete graph with a time and a toll associated with each edge, find a path from the first node to the last node within time constraint and minimize toll.</p>
  
  <p>As with any problems, there are many ways to solve it. My idea is to extend the Floyd-Warshall algorithm to keep track of all non-dominated paths. At the end of the algorithm, we extract the path with minimal cost, and if there are multiple paths with the same cost, choose the one that spent least time.</p>
  
  <p>Complexity aside, the bad thing is, wrong answer. I have no idea what is wrong. I have generated some random graphs and used a brute force solver (one that try all possible paths) and they matches exactly on small (i.e. less than 11 nodes) graphs. Without further ado, here is the code:</p>
  
  <pre><code>#include "stdafx.h"
  
  // http://www.spoj.com/problems/FISHER/
  
  // #define LOG
  
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;map&gt;
  #include &lt;algorithm&gt;
  
  using namespace std;
  
  int main()
  {
      while (true)
      {
          int num_cities;
          int time_budget;
          vector&lt;vector&lt;int&gt; &gt; distances;
          vector&lt;vector&lt;int&gt; &gt; tolls;
  
          cin &gt;&gt; num_cities;
          cin &gt;&gt; time_budget;
          if (num_cities == 0 &amp;&amp; time_budget == 0)
          {
              break;
          }
          distances.resize(num_cities);
          tolls.resize(num_cities);
          for (int i = 0; i &lt; num_cities; i++)
          {
              distances[i].resize(num_cities);
              tolls[i].resize(num_cities);
          }
          for (int i = 0; i &lt; num_cities; i++)
          {
              for (int j = 0; j &lt; num_cities; j++)
              {
                  int distance;
                  cin &gt;&gt; distance;
                  distances[i][j] = distance;
              }
          }
          for (int i = 0; i &lt; num_cities; i++)
          {
              for (int j = 0; j &lt; num_cities; j++)
              {
                  int toll;
                  cin &gt;&gt; toll;
                  tolls[i][j] = toll;
              }
          }
  
          // Try Floyd Warshall
          // Denote the set of shortest paths from i to j going through {0,1,...k - 1} be shortest_paths[i][j][k], 
          // It is a set of shortest paths because there can be multiple shortest paths with different time used.
          // We should record if using longer time can lead to lower cost, or similarly higher cost but less time
          // The first element in the pair is the cost, the second element in the pair is time used
          vector&lt;vector&lt;vector&lt;vector&lt;pair&lt;int, int&gt; &gt; &gt; &gt; &gt; shortest_paths;
          shortest_paths.resize(num_cities);
          for (int i = 0; i &lt; num_cities; i++)
          {
              shortest_paths[i].resize(num_cities);
              for (int j = 0; j &lt; num_cities; j++)
              {
                  shortest_paths[i][j].resize(num_cities + 1);
              }
          }
  
          // Initialization - there is only one path without going through any node
  #ifdef LOG
          cout &lt;&lt; "k = " &lt;&lt; 0 &lt;&lt; endl;
          cout &lt;&lt; "&lt;table border='1'&gt;" &lt;&lt; endl;
  #endif
          for (int i = 0; i &lt; num_cities; i++)
          {
  #ifdef LOG
              cout &lt;&lt; "&lt;tr&gt;" &lt;&lt; endl;
  #endif
  
              for (int j = 0; j &lt; num_cities; j++)
              {
  #ifdef LOG
                  cout &lt;&lt; "&lt;td&gt;(" &lt;&lt; tolls[i][j] &lt;&lt; ", " &lt;&lt; distances[i][j] &lt;&lt; ")&lt;/td&gt;";
  #endif
                  shortest_paths[i][j][0].push_back(pair&lt;int, int&gt;(tolls[i][j], distances[i][j]));
              }
  #ifdef LOG
              cout &lt;&lt; "&lt;/tr&gt;" &lt;&lt; endl;
  #endif
          }
  #ifdef LOG
          cout &lt;&lt; "&lt;/table&gt;" &lt;&lt; endl;
  #endif
          // Iteration - the shortest path
          for (int k = 1; k &lt;= num_cities; k++)
          {
  #ifdef LOG
              cout &lt;&lt; "k = " &lt;&lt; k &lt;&lt; endl;
              cout &lt;&lt; "&lt;table border='1'&gt;" &lt;&lt; endl;
  #endif
              for (int i = 0; i &lt; num_cities; i++)
              {
  #ifdef LOG
                  cout &lt;&lt; "&lt;tr&gt;";
  #endif
                  for (int j = 0; j &lt; num_cities; j++)
                  {
                      // Step 1: Generate all candidate shortest paths
                      map&lt;pair&lt;int, int&gt;, bool&gt; candidates;
                      for (vector&lt;pair&lt;int, int&gt; &gt;::iterator pi = shortest_paths[i][j][k - 1].begin(); pi != shortest_paths[i][j][k - 1].end(); pi++)
                      {
                          candidates.insert(pair&lt;pair&lt;int, int&gt;, bool&gt;(*pi, false));
                      }
                      for (vector&lt;pair&lt;int, int&gt; &gt;::iterator fi = shortest_paths[i][k - 1][k - 1].begin(); fi != shortest_paths[i][k - 1][k - 1].end(); fi++)
                      {
                          for (vector&lt;pair&lt;int, int&gt; &gt;::iterator si = shortest_paths[k - 1][j][k - 1].begin(); si != shortest_paths[k - 1][j][k - 1].end(); si++)
                          {
                              int first_path_cost = fi-&gt;first;
                              int first_path_time_used = fi-&gt;second;
                              int second_path_cost = si-&gt;first;
                              int second_path_time_used = si-&gt;second;
  
                              int new_path_cost = first_path_cost + second_path_cost;
                              int new_path_time_used = first_path_time_used + second_path_time_used;
  
                              if (new_path_time_used &lt;= time_budget)
                              {
                                  candidates.insert(pair&lt;pair&lt;int, int&gt;, bool&gt;(pair&lt;int, int&gt;(new_path_cost, new_path_time_used), false));
                              }
                          }
                      }
  
                      vector&lt;pair&lt;pair&lt;int, int&gt;, bool&gt; &gt; candidates_list;
                      for (map&lt;pair&lt;int,int&gt;, bool&gt;::iterator ci = candidates.begin(); ci != candidates.end(); ci++)
                      {
                          candidates_list.push_back(*ci);
                      }
  
                      // Eliminate the bad ones
                      for (unsigned int p = 0; p &lt; candidates_list.size(); p++)
                      {
                          for (unsigned int q = 0; q &lt; candidates_list.size(); q++)
                          {
                              if (p != q)
                              {
                                  int first_path_cost = candidates_list[p].first.first;
                                  int first_path_time_used = candidates_list[p].first.second;
                                  int second_path_cost = candidates_list[q].first.first;
                                  int second_path_time_used = candidates_list[q].first.second;
  
                                  // First take less time and less cost than second, second is eliminated
                                  if (first_path_time_used &lt;= second_path_time_used &amp;&amp; first_path_cost &lt;= second_path_cost)
                                  {
                                      candidates_list[q].second = true;
                                  }
                              }
                          }
                      }
  #ifdef LOG
                      cout &lt;&lt; "&lt;td&gt;";
  #endif
                      for (unsigned int p = 0; p &lt; candidates_list.size(); p++)
                      {
                          if (candidates_list[p].second == false)
                          {
  #ifdef LOG
                              cout &lt;&lt; "(" &lt;&lt; candidates_list[p].first.first &lt;&lt; ", " &lt;&lt; candidates_list[p].first.second &lt;&lt; ")&lt;br&gt;";
  #endif
                              shortest_paths[i][j][k].push_back(candidates_list[p].first);
                          }
                      }
  #ifdef LOG
                      cout &lt;&lt; "&lt;/td&gt;";
  #endif
  
                  }
  #ifdef LOG
                  cout &lt;&lt; "&lt;/tr&gt;" &lt;&lt; endl;;
  #endif
              }
  #ifdef LOG
              cout &lt;&lt; "&lt;/table&gt;" &lt;&lt; endl;
  #endif
          }
  
          bool first = true;
          int best_cost = -1;
          int best_cost_time = -1;
          for (vector&lt;pair&lt;int, int&gt; &gt;::iterator pi = shortest_paths[0][num_cities - 1][num_cities].begin(); pi != shortest_paths[0][num_cities - 1][num_cities].end(); pi++)
          {
              if (first)
              {
                  best_cost = pi-&gt;first;
                  best_cost_time = pi-&gt;second;
                  first = false;
              }
              else
              {
                  if (pi-&gt;first &lt; best_cost)
                  {
                      best_cost = pi-&gt;first;
                      best_cost_time = pi-&gt;second;
                  }
                  if (pi-&gt;first == best_cost &amp;&amp; pi-&gt;second &lt; best_cost_time)
                  {
                      best_cost_time = pi-&gt;second;
                  }
              }
          }
          cout &lt;&lt; best_cost &lt;&lt; " " &lt;&lt; best_cost_time &lt;&lt; endl;
      }
  
      return 0;
  
  }
  /*
  4 7
  0 5 2 3
  5 0 2 3
  3 1 0 2
  3 3 2 0
  
  0 2 2 7
  2 0 1 2
  2 2 0 5
  7 2 5 0
  
  0 0
  
  */
  </code></pre>
  
  <p>Turn on the LOG you will be able to see the Floyd Warshall table for each iteration, each cell has set of a (cost, time) pair. They are supposed to be the cost/time pairs of all non-dominated paths.</p>
  
  <p>I would really appreciate if someone can tell me what's wrong. Thanks a lot in advance!</p>