#include <ctime>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const char DELIMITER = '/'; // Delimiter character for the correct accumulation of order
const unsigned int TIME_CONVERSION_CONSTANT = 1000; // Used to converting the time, in milliseconds in this case
struct Visa {
vector <unsigned int> listOfSubordinatesForBribe; // Storage of subordinates' indices whose signature is required
double bribe; // Required bribe
};
struct Official {
unsigned int id; // Official id (sequence number in the input stream, starting at one)
vector <Visa> listOfRequiredVisas; // Storage of possible variants of visas
};
bool isBypassed(Official currentOfficial, string order) { // Return true, if this official is already bypassed
bool isBypassed = false;
for (auto currentVisa : currentOfficial.listOfRequiredVisas) {
for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
if (order.find(to_string(currentSubordinate) + DELIMITER) != string::npos) { // We are looking we are looking for the presence of at least one subordinate including a separator
isBypassed = true; // In the string of previously accumulated order of bypass
break;
}
}
}
return isBypassed;
}
void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &order, unsigned int &minimumBribe) {
vector <unsigned int> possibleSumsOfBribes; // Stores all the possible sums of bribes for the current official
vector <string> possibleOrdersOfBypassing; // Stores all the possible orders for the current of
if (!currentOfficial.listOfRequiredVisas.empty() && !isBypassed(currentOfficial, order)) {
int currentSumOfBribes = 0; // Current sum of bribes for current official
for (auto currentVisa : currentOfficial.listOfRequiredVisas) {
for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
findCheapestWay(listOfOfficials, listOfOfficials[currentSubordinate], order, minimumBribe); // Recursively call the function for finding the minimum required bribe
currentSumOfBribes = minimumBribe; // Store the detected minimum as a current
} // For each official we get down to the lower level
string currentOrder; // Remember all the officials, that we bypassed to the current bribe
currentSumOfBribes = currentVisa.bribe; // Remember the bribe required by the current official as the current sum of bribes
for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
currentOrder += to_string(currentSubordinate) + DELIMITER;
} // Remember the current oder for each visa (isn't necessary an order to get the minimum sum of bribes) with delimiter
possibleOrdersOfBypassing.push_back(order + currentOrder); // Adding one of the possible orders, including previously accumulated value
possibleSumsOfBribes.push_back(minimumBribe + currentSumOfBribes); // Adding one of the possible sums, including value that we get from lower level
} // Executes processing for each visa in visas list
vector<unsigned int>::iterator iteratorToCurrentMinBribe = min_element(possibleSumsOfBribes.begin(), possibleSumsOfBribes.end());
unsigned int indexOfCurrentMinBribe = distance(possibleSumsOfBribes.begin(), iteratorToCurrentMinBribe);// Find the index of the lowest possible variant in the resulting vector
minimumBribe = possibleSumsOfBribes[indexOfCurrentMinBribe]; // This variant will be the smallest by sum of bribes, remember it
order = possibleOrdersOfBypassing[indexOfCurrentMinBribe]; // And remember corresponding to minimum bribe order
} // Executes processing only if the list of visas isn't empty and the official isn't bypassed
}
int main() {
clock_t startTime;
ios_base::sync_with_stdio(false);
string order; // The order of bypass, that we're looking for
string typeOfCommand; // Technical variable for processing the input stream
unsigned int quantityOfOfficials; // User-defined number of officials
unsigned int minimumBribe = 0; // Minimum sum of bribes to get a license
cin >> quantityOfOfficials;
Official *listOfOfficials = new Official[quantityOfOfficials + 1]; // Keeps all the officials in the array with the corresponding index
unsigned int indexOfOfficial = 1;
while (cin >> typeOfCommand) {
Official currentOfficial;
while (typeOfCommand != "next_official") {
Visa currentVisa;
vector <unsigned int> requiredSubordinates;
while (typeOfCommand != "bribe") {
requiredSubordinates.push_back(atoi(typeOfCommand.c_str())); // Before recording convert the input string to the number
cin >> typeOfCommand;
} // Read the current visa (indices of subbordinates for bribe)
currentVisa.listOfSubordinatesForBribe = requiredSubordinates;
cin >> typeOfCommand; // Read directly bribe
currentVisa.bribe = atoi(typeOfCommand.c_str()); // Before recording convert the input string to the number
currentOfficial.listOfRequiredVisas.push_back(currentVisa); // Add current visa to the current official visas list
cin >> typeOfCommand;
} // Read the current official
currentOfficial.id = indexOfOfficial;
listOfOfficials[indexOfOfficial] = currentOfficial; // Put all the read data into an array
indexOfOfficial++; // Go to read the next official, if present
} // Read to the end of the input stream
findCheapestWay(listOfOfficials, listOfOfficials[1], order, minimumBribe); // Call the function from main official(first) and accumulate the required values
order.push_back('1'); // Add the first official explicitly, cause he hasn't chief, so doesn't participate in the bypassing
cout << minimumBribe << endl << order << endl;
cout << "Working time: " << (clock() - startTime) / (double) (CLOCKS_PER_SEC / TIME_CONVERSION_CONSTANT) << " ms" << endl;
return 0;
}