Can someone post some sample data that this doesn't work with? I know a lot of people haven't solved this, but it looks like I have almost.
Code: Select all
/* @JUDGE_ID: xxxxxx 205 C++ */
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
struct Flight
{
string toName;
int to;
int departure;
int arrival;
double cost;
};
struct City
{
string name;
vector<Flight> flights;
City()
{
}
City(string name) : name(name)
{
}
};
string itoa(int x)
{
string s;
if (x == 0)
return "0";
int y = 1;
while (x / y)
y *= 10;
while (y /= 10)
s.push_back('0' + (x / y) % 10);
return s;
}
string translateTime(int t)
{
string s;
int d = t / 1440;
int h = t / 60 % 24;
int m = t % 60;
char buff[80];
if (d)
{
s += itoa(d) + " day";
if (d > 1)
s.push_back('s');
s.push_back(' ');
}
s += itoa(h) + ":";
s.push_back('0' + m/10);
s.push_back('0' + m%10);
return s;
}
string translateTOD(int t)
{
string s = translateTime(t % 720);
s.push_back((t%1440) >= 720 ? 'P' : 'A');
return s;
}
string rightPad(string s, int width)
{
while (s.size() < width)
s.push_back(' ');
return s;
}
string leftPad(string s, int width)
{
string space;
while (s.size() < width)
{
space.push_back(' ');
width--;
}
return space + s;
}
void normalize(string &s)
{
transform(s.begin(), s.end(), s.begin(), tolower);
s[0] = toupper(s[0]);
}
int timeAfter(int t, int d)
{
while (d <= t)
d += 1440;
return d;
}
string translateCost(double d)
{
string s = "$";
s += itoa(int(floor(d)));
int x = int(floor(d * 100));
s.push_back('.');
s.push_back('0' + (x / 10) % 10);
s.push_back('0' + (x % 10));
return s;
}
struct Graph
{
vector<City> cities;
map<string, int> numbers;
void resolveFlights()
{
for (int i = 0; i < cities.size(); i++)
numbers[cities[i].name] = i;
for (int i = 0; i < cities.size(); i++)
for (int j = 0; j < cities[i].flights.size(); j++)
cities[i].flights[j].to =
numbers[cities[i].flights[j].toName];
}
void bestRoute(string fromName, string toName, string opt)
{
normalize(toName); normalize(fromName); normalize(opt);
if (fromName == toName)
{
cout << "You are already in " << toName << "." << endl;
return;
}
bool byCost = opt == "Cost";
int from = numbers[fromName];
int to = numbers[toName];
int cityNum = from;
double cost[20];
int route[20];
int flight[20];
int time[20];
bool visited[20];
for (int i = 0; i < cities.size(); i++)
{
cost[i] = 1000000;
time[i] = 1000000;
visited[i] = false;
route[i] = -1;
flight[i] = -1;
}
time[from] = 0;
cost[from] = 0;
route[from] = -1;
flight[from] = -1;
while (cityNum != to)
{
City &city = cities[cityNum];
visited[cityNum] = true;
int t = time[cityNum];
double c = cost[cityNum];
for (int i = 0; i < city.flights.size(); i++)
{
int toCity = city.flights[i].to;
int dep = timeAfter(time[cityNum],
city.flights[i].departure);
int arr = dep - city.flights[i].departure +
city.flights[i].arrival;
double co = c + city.flights[i].cost;
bool fly;
fly = byCost ?
(cost[toCity] > co ||
(cost[toCity]==co && time[toCity]>arr))
:
(time[toCity]>arr ||
(time[toCity]==arr&&cost[toCity]>co));
if (fly)
{
cost[toCity] = co;
time[toCity] = arr;
route[toCity] = cityNum;
flight[toCity] = i;
}
}
int best = 0;
while (best < cities.size() && visited[best])
best++;
for (int i = best+1; i < cities.size(); i++)
if (!visited[i])
{
if (byCost)
{
if (cost[i] < cost[best])
best = i;
}
else
if (time[i] < time[best])
best = i;
}
cityNum = best;
}
vector<int> fullRoute;
cityNum = to;
while (cityNum >= 0 && cityNum != from)
{
fullRoute.push_back(cityNum);
cityNum = route[cityNum];
}
if (cityNum < 0)
{
cout << "There is no route from " << fromName <<
" to " << toName << "." << endl;
return;
}
cout << "From: " << rightPad(fromName, 20) <<
" To: " << rightPad(toName, 20)<<
" Optimize: " << opt << endl <<
"================================="
"=================================" << endl <<
"From To "
" Leave Arrive Cost" << endl <<
"================================="
"=================================" << endl;
int f = from;
int curTime = 0;
int startTime = cities[f].flights[flight[fullRoute.back()]].
departure;
double totalCost = 0;
while (fullRoute.size())
{
int t = fullRoute.back();
fullRoute.pop_back();
Flight &fl = cities[f].flights[flight[t]];
cout << rightPad(cities[f].name, 20) <<
rightPad(cities[t].name, 23) <<
rightPad(translateTOD(fl.departure), 8) <<
rightPad(translateTOD(fl.arrival), 8) <<
leftPad(translateCost(fl.cost), 7) <<
endl;
totalCost += fl.cost;
curTime = timeAfter(curTime-1, fl.departure);
curTime = timeAfter(curTime, fl.arrival);
f = t;
}
cout << " "
" -----------------------" << endl <<
leftPad(translateTime(curTime - startTime), 57) <<
leftPad(translateCost(totalCost), 9) << endl;
}
};
int readTime(istream &in)
{
int h;
in >> h;
in.ignore(1);
int m;
in >> m;
if (in.get() == 'P')
h += 12;
return h * 60 + m;
}
istream &operator>>(istream &in, Flight &f)
{
in >> f.toName;
normalize(f.toName);
f.departure = readTime(in);
f.arrival = timeAfter(f.departure, readTime(in));
return in >> f.cost;
}
istream &operator>>(istream &in, Graph &g)
{
g.cities.resize(0);
map<string, City> cities;
string from;
while (in >> from && from != "#")
{
normalize(from);
City &city = cities[from];
city.name = from;
Flight f;
in >> f;
cities[f.toName].name = f.toName;
city.flights.push_back(f);
}
map<string, City>::iterator city;
for (city = cities.begin(); city != cities.end(); city++)
g.cities.push_back(city->second);
g.resolveFlights();
return in;
}
int main(int argc, char *argv[])
{
string travel;
bool first = true;
while (cin >> travel)
{
int id;
cin >> id;
if (!first)
cout << endl << endl;
first = false;
cout << "Requests and optimal routes for travel " << id <<
endl <<
"------------------------------------------" << endl <<
endl;
Graph g;
cin >> g;
bool first2 = true;
string s;
while (cin >> s && cin && s != "#")
{
string d, opt;
cin >> d >> opt;
if (!first2)
cout << endl;
first2 = false;
g.bestRoute(s, d, opt);
}
}
return 0;
}
. I tried a lot and i can't find the bug and also I don't know how the total time has to displayed if there are less than 60 mins like 0:10 or 10