I'm trying to solve the arbitrage problem, but it's not behaving as expected. It's worked fine for all the sample data I found on this forum, but I'm still getting a WA on submit. Can someone help me? It's C++, by the way.
Code: Select all
// Arbitrage
#include <iostream>
#include <sstream>
#include <stack>
using namespace std;
#define MAX 20
#define EPS 0.000001
string intToString(int x)
{
ostringstream ss;
ss << x;
return ss.str();
}
// Floyd-Warshall Algorithm
string FW(double table[MAX][MAX], int numCountries)
{
string output;
// Initialize the tables
double best[MAX][MAX][MAX];
int path[MAX][MAX][MAX];
for (int i = 0; i < numCountries; i++)
for (int j = 0; j < numCountries; j++)
for (int k = 0; k < numCountries; k++)
{
best[i][j][k] = 0;
if (k == 1)
{
best[i][j][k] = table[i][j];
path[i][j][k] = i;
}
}
// Begin the search
for (int steps = 2; steps <= numCountries; steps++)
{
for (int k = 0; k < numCountries; k++)
{
for (int i = 0; i < numCountries; i++)
for (int j = 0; j < numCountries; j++)
{
double temp = best[i][k][steps-1] * best[k][j][1];
if (temp > best[i][j][steps])
{
best[i][j][steps] = temp;
path[i][j][steps] = k;
}
}
}
for (int i = 0; i < numCountries; i++)
{
if (best[i][i][steps] - 1.01 > EPS)
{
stack<int> s;
s.push(i);
int next = i;
for (int j = steps; j > 0; j--)
{
next = path[i][next][j];
s.push(next);
}
output = intToString(s.top() + 1);
s.pop();
while(!s.empty())
{
output += " ";
output += intToString(s.top() + 1);
s.pop();
}
output += "\n";
return output;
}
}
}
return "no arbitrage sequence exists\n";
}
string findSeq(double table[MAX][MAX], int numCountries)
{
double best[MAX][MAX];
return FW(table, numCountries);
}
int main()
{
string input, output;
int numCountries;
while (true)
{
getline(cin, input);
if (input == "")
{
break;
}
numCountries = atoi(input.c_str());
double table[MAX][MAX];
for (int row = 0; row < numCountries; row++)
{
getline(cin, input);
istringstream *ss = new istringstream;
ss->str(input);
for (int col = 0; col < numCountries; col++)
{
if (row == col)
{
table[row][col] = 1.0;
}
else
{
*ss >> table[row][col];
}
}
delete ss;
}
output += findSeq(table, numCountries);
}
cout << output;
}