#include #include #include #include #include #include struct node{ node(int targetCity, int price):targetCity(targetCity),price(price){} int targetCity; int price; }; struct inputNode { inputNode(int numOfProducts, int idOfCrane, int price) { this->numOfProducts = numOfProducts; this->idOfCrane = idOfCrane; this->price = price; } int numOfProducts; int idOfCrane; int price; }; int main() { int numOfCities; std::cin >> numOfCities; std::multimap input;//numOfCity, inputnode std::multimap path;//startCity -> node //INPUT for (int cityID = 0; cityID < numOfCities; ++cityID) { int numOfCranes; std::cin>>numOfCranes; int idOfCrane, priceInTheCity; for (int i = 0; i < numOfCranes; ++i) { std::cin>>idOfCrane >> priceInTheCity; input.emplace(cityID,inputNode(numOfCranes,idOfCrane, priceInTheCity));//tohle bude sedet na pozici [] } } // PLNENI MAPY for (int first = 0; first < numOfCities; ++first) { for (int second = first; second < numOfCities; ++second) { auto firstCity = input.find(first); for (auto i = firstCity; i != input.end() && i->first == first; ++i) {//vsechny itemy ve meste auto secondCity = input.find(second); for (auto j = secondCity; j != input.end() && j->first == second ; ++j) { int price = j->second.price - i->second.price; if( price > 0) path.emplace(first,node(second,price)); } } } } // for (auto i = input.find(first); i != input.end() && i->first == first ; i++) {//projet vsechny crane // // int tmpPrice = i->second.price - i->second.price; // if(tmpPrice <= 0 || i->second.idOfCrane != i->second.idOfCrane) // continue; // path.emplace(first,node(second, tmpPrice)); // } // } // } //BFS std::map bfsResult;//mesto, vydelek std::queue bfsqueue; for(auto i : path) bfsqueue.emplace(i.first);//pridam vsechny body, ke se vyplati neco vyzvednout while(!bfsqueue.empty()){ int city = bfsqueue.front();//mesto ve kterym ted jsem bfsqueue.pop(); //pridat vsechny mesta na dosah do fronty, zaroven k nim ulozit do mapy hodnoty int price = 0; auto res = bfsResult.find(city); if(res != bfsResult.end()){ price = res->second;//nejvetsi vydelek, kterym jsem se do tohoto mesta dostal } //projit vsechny mesta na dosah for (auto i = path.find(city); i != path.end() && i->first == city ; ++i) {//mesta kam pujdu int targetCity = i->second.targetCity; bfsqueue.push(targetCity);//podivam se tam v pristim bfs auto inBfsRes = bfsResult.find(targetCity); if(inBfsRes == bfsResult.end()){//pokud jsem tam jeste nebyl pridat to bfsResult.emplace(targetCity, (price + i->second.price)); }else{ if(price + i->second.price > inBfsRes->second) inBfsRes->second = price + i->second.price; } } } //find max int max = 0; for(auto i : bfsResult) if(i.second > max) max = i.second; std::cout << max; return 0; }