177 lines
4.5 KiB
C++
177 lines
4.5 KiB
C++
#include <sstream>
|
|
#include <string>
|
|
#include <algorithm>
|
|
#include <map>
|
|
#include <set>
|
|
#include <list>
|
|
#include <deque>
|
|
#include <queue>
|
|
#include <stack>
|
|
#include <cassert>
|
|
#include <memory>
|
|
using namespace std;
|
|
|
|
// https://fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/bi-pa2/pa2_zkou%C5%A1ka_2019-05-23
|
|
|
|
class CMHD {
|
|
using Stop = int;
|
|
struct Line {
|
|
std::vector<Stop> _s;
|
|
};
|
|
using ALine = std::shared_ptr<Line>;
|
|
|
|
|
|
public:
|
|
void Add ( istringstream & is )
|
|
{
|
|
ALine l(new Line());
|
|
|
|
string str;
|
|
while ( getline(is, str) ) {
|
|
Stop s = addStop(str);
|
|
_lines[s].push_back(l);
|
|
l->_s.push_back(s);
|
|
}
|
|
}
|
|
|
|
//===============================================================================
|
|
|
|
set < string > Dest ( const string & from, int maxCost ) const {
|
|
Stop start = findStop(from);
|
|
if (start == -1)
|
|
return { "unknown" };
|
|
|
|
std::set< std::string > ret;
|
|
std::map< ALine, int > d;
|
|
std::queue< ALine > q;
|
|
|
|
for (const auto& i : _lines[start]) {
|
|
d[i] = 0;
|
|
q.emplace(i);
|
|
}
|
|
|
|
while (q.size()) {
|
|
auto i = q.front();
|
|
q.pop();
|
|
|
|
if (d[i] > maxCost) continue;
|
|
|
|
for (Stop s : i->_s) {
|
|
ret.emplace( _names[s] );
|
|
for ( const ALine& l : _lines[s]) {
|
|
auto it = d.try_emplace(l, d[i] + 1);
|
|
if (it.second) {
|
|
q.emplace(l);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return ret;
|
|
}
|
|
|
|
//===============================================================================
|
|
private:
|
|
|
|
inline Stop addStop( const std::string& s ) {
|
|
auto it = _stops.try_emplace(s, _stops.size());
|
|
if (it.second) {
|
|
_names.emplace_back(s);
|
|
_lines.emplace_back();
|
|
}
|
|
return it.first->second;
|
|
};
|
|
|
|
inline Stop findStop( const std::string& s ) const {
|
|
auto it = _stops.find(s);
|
|
return it == _stops.end() ? -1 : it->second;
|
|
};
|
|
|
|
// str -> stop
|
|
std::map< std::string, Stop > _stops;
|
|
|
|
// stop -> str
|
|
std::vector< std::string > _names;
|
|
|
|
// stop -> lines
|
|
std::vector< std::vector < ALine > > _lines;
|
|
};
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
int main ( void )
|
|
{
|
|
CMHD city;
|
|
istringstream iss;
|
|
iss.clear();
|
|
|
|
iss . str ( "A\nB\nC\nD\nE\n" );
|
|
city . Add ( iss );
|
|
iss . clear();
|
|
|
|
iss . str ( "B\nC\nF\nH\n" );
|
|
city . Add ( iss );
|
|
iss . clear();
|
|
|
|
iss . str ( "F\nG\nI\nJ\nK\nN\n" );
|
|
city . Add ( iss );
|
|
iss . clear();
|
|
|
|
iss . str ( "H\nL\n" );
|
|
city . Add ( iss );
|
|
iss . clear();
|
|
|
|
iss . str ( "L\nM\nN\nO\n" );
|
|
city . Add ( iss );
|
|
iss . clear();
|
|
|
|
iss . str ( "P\nQ\nR\nN\nS" );
|
|
city . Add ( iss );
|
|
iss . clear();
|
|
|
|
assert ( city . Dest ( "S", 0 ) == set < string > ( {"S", "N", "R", "Q", "P"} ) );
|
|
|
|
assert ( city . Dest ( "S", 1 ) == set < string > ( { "S", "N", "R", "Q", "P",
|
|
"O", "M", "L",
|
|
"K", "J", "I", "G", "F" } ) );
|
|
|
|
assert ( city . Dest ( "N", 0 ) == set < string > ( { "S", "N", "R", "Q", "P",
|
|
"O", "M", "L",
|
|
"K", "J", "I", "G", "F" } ) );
|
|
|
|
assert ( city . Dest ( "N", 1 ) == set < string > ( { "S", "N", "R", "Q", "P",
|
|
"O", "M", "L",
|
|
"K", "J", "I", "G", "F",
|
|
"H", "F", "C", "B" } ) );
|
|
|
|
assert ( city . Dest ( "N", 2 ) == set < string > ( { "S", "N", "R", "Q", "P",
|
|
"O", "M", "L",
|
|
"K", "J", "I", "G", "F",
|
|
"H", "F", "C", "B",
|
|
"A", "D", "E" } ) );
|
|
|
|
assert ( city . Dest ( "unknown", 0 ) == set < string > ( { "unknown" } ) );
|
|
assert ( city . Dest ( "unknown", 1 ) == set < string > ( { "unknown" } ) );
|
|
assert ( city . Dest ( "unknown", 2 ) == set < string > ( { "unknown" }) );
|
|
|
|
return 0;
|
|
} |