1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include "CityVisit.h"
CityVisit::~CityVisit() {
for (Landmark* l : landmarks)
delete l;
}
CityVisit::Landmark* CityVisit::find(const std::string& name) {
for (Landmark* l : landmarks) {
if (l->name == name)
return l;
}
return nullptr;
}
void CityVisit::pushLandmarks(const std::string& from, const std::string& to, unsigned time) {
Landmark* a = find(from);
if (a == nullptr) {
a = new Landmark(from);
landmarks.push_back(a);
}
Landmark* b = find(to);
if (b == nullptr) {
b = new Landmark(to);
landmarks.push_back(b);
}
a->visitable.push_back({ b, time });
b->visitable.push_back({ a, time });
}
void CityVisit::parse(std::ifstream& inFile) {
unsigned k = 0, r = 0;
inFile >> k >> r;
std::string name1;
std::string name2;
unsigned time = 0;
while (r-- > 0) {
inFile >> name1 >> name2 >> time;
pushLandmarks(name1, name2, time);
}
inFile >> availableTime;
}
void CityVisit::visitTheMostInTimeRec(Landmark* currentLandmark, std::deque<Landmark*> currPath, std::deque<Landmark*> unique, int timeLeft, std::deque<Landmark*>& bestPath, unsigned& uniqueCount) {
if (timeLeft < 0) return;
bool currentExists = false;
for (const Landmark* l : unique) {
if (l == currentLandmark) {
currentExists = true;
break;
}
}
if (!currentExists)
unique.push_back(currentLandmark);
currPath.push_back(currentLandmark);
if (currentLandmark->name == "Railstation" && unique.size() > uniqueCount) {
bestPath = currPath;
uniqueCount = unique.size();
}
for (auto lp : currentLandmark->visitable) {
visitTheMostInTimeRec(lp.first, currPath, unique, timeLeft - lp.second, bestPath, uniqueCount);
}
}
std::deque<std::string> CityVisit::visitTheMostInTime(std::ifstream& inFile) {
landmarks.clear();
parse(inFile);
Landmark* station = find("Railstation");
if (station == nullptr)
throw std::logic_error("No landmark named Railstation exists!");
std::deque<Landmark*> outLandmarks;
unsigned uniqueCount = 0;
visitTheMostInTimeRec(station, std::deque<Landmark*>(), std::deque<Landmark*>(), availableTime, outLandmarks, uniqueCount);
std::deque<std::string> out;
for (Landmark* l : outLandmarks) {
out.push_back(l->name);
}
return out;
}
|
