为什么我不断为WA获得SPOJ FISHER的解决方案？

Question

我想解决这个问题，我想我已经拿出了一个正确的答案，但我一直在得到法官的WA（错误答案）回复。

http://www.spoj.com/problems/FISHER/

问题蒸馏，给定一个完整的图表，时间以及与每个边缘相关联收费，找到从第一节点到最后一个节点时间约束内的路径和最小化的代价。

与任何问题一样，有很多方法可以解决它。我的想法是扩展Floyd-Warshall算法以跟踪所有非主导路径。在算法结束时，我们以最小的成本提取路径，并且如果有多条路径具有相同的成本，请选择花费最少的路径。

除了复杂性外，坏事就是错误的答案。我不知道什么是错的。我已经生成了一些随机图并使用了一个蛮力解算器（一个可以尝试所有可能路径的解算器），它们恰好在小（即少于11个节点）图上匹配。事不宜迟，这里是代码：

#include "stdafx.h" 

// http://www.spoj.com/problems/FISHER/ 

// #define LOG 

#include <iostream> 
#include <vector> 
#include <map> 
#include <algorithm> 

using namespace std; 

int main() 
{ 
    while (true) 
    { 
     int num_cities; 
     int time_budget; 
     vector<vector<int> > distances; 
     vector<vector<int> > tolls; 

     cin >> num_cities; 
     cin >> time_budget; 
     if (num_cities == 0 && time_budget == 0) 
     { 
      break; 
     } 
     distances.resize(num_cities); 
     tolls.resize(num_cities); 
     for (int i = 0; i < num_cities; i++) 
     { 
      distances[i].resize(num_cities); 
      tolls[i].resize(num_cities); 
     } 
     for (int i = 0; i < num_cities; i++) 
     { 
      for (int j = 0; j < num_cities; j++) 
      { 
       int distance; 
       cin >> distance; 
       distances[i][j] = distance; 
      } 
     } 
     for (int i = 0; i < num_cities; i++) 
     { 
      for (int j = 0; j < num_cities; j++) 
      { 
       int toll; 
       cin >> 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<vector<vector<vector<pair<int, int> > > > > shortest_paths; 
     shortest_paths.resize(num_cities); 
     for (int i = 0; i < num_cities; i++) 
     { 
      shortest_paths[i].resize(num_cities); 
      for (int j = 0; j < 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 << "k = " << 0 << endl; 
     cout << "<table border='1'>" << endl; 
#endif 
     for (int i = 0; i < num_cities; i++) 
     { 
#ifdef LOG 
      cout << "<tr>" << endl; 
#endif 

      for (int j = 0; j < num_cities; j++) 
      { 
#ifdef LOG 
       cout << "<td>(" << tolls[i][j] << ", " << distances[i][j] << ")</td>"; 
#endif 
       shortest_paths[i][j][0].push_back(pair<int, int>(tolls[i][j], distances[i][j])); 
      } 
#ifdef LOG 
      cout << "</tr>" << endl; 
#endif 
     } 
#ifdef LOG 
     cout << "</table>" << endl; 
#endif 
     // Iteration - the shortest path 
     for (int k = 1; k <= num_cities; k++) 
     { 
#ifdef LOG 
      cout << "k = " << k << endl; 
      cout << "<table border='1'>" << endl; 
#endif 
      for (int i = 0; i < num_cities; i++) 
      { 
#ifdef LOG 
       cout << "<tr>"; 
#endif 
       for (int j = 0; j < num_cities; j++) 
       { 
        // Step 1: Generate all candidate shortest paths 
        map<pair<int, int>, bool> candidates; 
        for (vector<pair<int, int> >::iterator pi = shortest_paths[i][j][k - 1].begin(); pi != shortest_paths[i][j][k - 1].end(); pi++) 
        { 
         candidates.insert(pair<pair<int, int>, bool>(*pi, false)); 
        } 
        for (vector<pair<int, int> >::iterator fi = shortest_paths[i][k - 1][k - 1].begin(); fi != shortest_paths[i][k - 1][k - 1].end(); fi++) 
        { 
         for (vector<pair<int, int> >::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->first; 
          int first_path_time_used = fi->second; 
          int second_path_cost = si->first; 
          int second_path_time_used = si->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 <= time_budget) 
          { 
           candidates.insert(pair<pair<int, int>, bool>(pair<int, int>(new_path_cost, new_path_time_used), false)); 
          } 
         } 
        } 

        vector<pair<pair<int, int>, bool> > candidates_list; 
        for (map<pair<int,int>, bool>::iterator ci = candidates.begin(); ci != candidates.end(); ci++) 
        { 
         candidates_list.push_back(*ci); 
        } 

        // Eliminate the bad ones 
        for (unsigned int p = 0; p < candidates_list.size(); p++) 
        { 
         for (unsigned int q = 0; q < 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 <= second_path_time_used && first_path_cost <= second_path_cost) 
           { 
            candidates_list[q].second = true; 
           } 
          } 
         } 
        } 
#ifdef LOG 
        cout << "<td>"; 
#endif 
        for (unsigned int p = 0; p < candidates_list.size(); p++) 
        { 
         if (candidates_list[p].second == false) 
         { 
#ifdef LOG 
          cout << "(" << candidates_list[p].first.first << ", " << candidates_list[p].first.second << ")<br>"; 
#endif 
          shortest_paths[i][j][k].push_back(candidates_list[p].first); 
         } 
        } 
#ifdef LOG 
        cout << "</td>"; 
#endif 

       } 
#ifdef LOG 
       cout << "</tr>" << endl;; 
#endif 
      } 
#ifdef LOG 
      cout << "</table>" << endl; 
#endif 
     } 

     bool first = true; 
     int best_cost = -1; 
     int best_cost_time = -1; 
     for (vector<pair<int, int> >::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->first; 
       best_cost_time = pi->second; 
       first = false; 
      } 
      else 
      { 
       if (pi->first < best_cost) 
       { 
        best_cost = pi->first; 
        best_cost_time = pi->second; 
       } 
       if (pi->first == best_cost && pi->second < best_cost_time) 
       { 
        best_cost_time = pi->second; 
       } 
      } 
     } 
     cout << best_cost << " " << best_cost_time << 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 

*/ 

打开的LOG，你将能够看到弗洛伊德沃肖尔表中的每个迭代，每个小区已形成集（成本，时间）对。它们应该是所有非主导路径的成本/时间对。

我真的很感激，如果有人能告诉我什么是错的。提前感谢！

Answer 1

你可以做个试验：

4 10 

0 1 1 1000 
1 0 1 1 
1 1 0 1 
1000 1 1 0 

0 1 1 1 
1 0 1 1 
1 1 0 1 
1 1 1 0 

基本上你需要确保distances[i][j] <= time_budget前

shortest_paths[i][j][0].push_back(pair<int, int>(tolls[i][j], distances[i][j]));