183 lines
4.7 KiB
C++
183 lines
4.7 KiB
C++
#ifndef __PROGTEST__
|
|
#include <cstdio>
|
|
#include <cstdlib>
|
|
#include <cstring>
|
|
#include <cctype>
|
|
#include <cassert>
|
|
#include <iostream>
|
|
#include <iomanip>
|
|
#include <sstream>
|
|
#include <stdexcept>
|
|
#include <string>
|
|
#include <list>
|
|
#include <vector>
|
|
#include <stack>
|
|
#include <queue>
|
|
#include <deque>
|
|
#include <map>
|
|
#include <unordered_map>
|
|
#include <set>
|
|
#include <unordered_set>
|
|
#include <algorithm>
|
|
#include <memory>
|
|
using namespace std;
|
|
#endif /* __PROGTEST__ */
|
|
|
|
// https://fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/bi-pa2/pa2_zkou%C5%A1ka_2023-05-25
|
|
|
|
class CTeleport {
|
|
public:
|
|
CTeleport() {}
|
|
~CTeleport() {}
|
|
|
|
enum City : int {};
|
|
enum Time : int {};
|
|
|
|
struct Port {
|
|
public:
|
|
Port( City to, Time fromTime, Time toTime )
|
|
: to(to), fromTime(fromTime), toTime(toTime) {}
|
|
|
|
City to;
|
|
Time fromTime;
|
|
Time toTime;
|
|
|
|
bool operator<( const Port& oth ) const {
|
|
return std::tie(fromTime, toTime, to) < std::tie(oth.fromTime, oth.toTime, oth.to);
|
|
}
|
|
};
|
|
|
|
//----------------------------------------------------------------------------
|
|
|
|
CTeleport & Add ( const string & from,
|
|
const string & to,
|
|
unsigned fromTime,
|
|
unsigned toTime )
|
|
{
|
|
auto it1 = _toInt.try_emplace(from, City(_toInt.size()));
|
|
if (it1.second) _ports.emplace_back();
|
|
|
|
auto it2 = _toInt.try_emplace(to, City(_toInt.size()));
|
|
if (it2.second) _ports.emplace_back();
|
|
|
|
_ports[ it1.first->second ].emplace(it2.first->second, Time(fromTime), Time(toTime));
|
|
|
|
return *this;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
|
|
CTeleport & Optimize ( void ) {
|
|
return *this;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
|
|
unsigned FindWay( const string & from, const string & to, unsigned time ) {
|
|
std::queue<City> q;
|
|
std::vector<Time> d(_toInt.size(), Time(-1));
|
|
|
|
auto it1 = _toInt.find(from);
|
|
auto it2 = _toInt.find(to);
|
|
|
|
if (it1 == _toInt.end() || it2 == _toInt.end()) throw std::invalid_argument("");
|
|
|
|
City start(it1->second);
|
|
City end(it2->second);
|
|
|
|
d[start] = Time(time);
|
|
q.push(start);
|
|
|
|
while (q.size()) {
|
|
City c = q.front();
|
|
q.pop();
|
|
Time t = d[c];
|
|
|
|
Port tmp(c, t, Time(0));
|
|
auto it = _ports[c].lower_bound(tmp);
|
|
while (it != _ports[c].end()) {
|
|
if (d[it->to] == -1 ||
|
|
d[it->to] > it->toTime) {
|
|
d[it->to] = it->toTime;
|
|
q.push(it->to);
|
|
}
|
|
++it;
|
|
}
|
|
}
|
|
|
|
if (d[end] != -1) return d[end];
|
|
|
|
throw std::invalid_argument("");
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
|
|
private:
|
|
std::map<std::string, City> _toInt;
|
|
std::vector< std::set<Port> > _ports;
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#ifndef __PROGTEST__
|
|
int main ( void )
|
|
{
|
|
CTeleport t;
|
|
t . Add ( "Prague", "Vienna", 0, 7 )
|
|
. Add ( "Vienna", "Berlin", 9, 260 )
|
|
. Add ( "Vienna", "London", 8, 120 )
|
|
. Add ( "Vienna", "Chicago", 4, 3 )
|
|
. Add ( "Prague", "Vienna", 10, 10 ) . Optimize ( );
|
|
|
|
assert ( t . FindWay ( "Prague", "Vienna", 0 ) == 7 );
|
|
assert ( t . FindWay ( "Prague", "Vienna", 1 ) == 10 );
|
|
assert ( t . FindWay ( "Prague", "London", 0 ) == 120 );
|
|
assert ( t . FindWay ( "Vienna", "Chicago", 4 ) == 3 );
|
|
|
|
try { t . FindWay ( "Prague", "London", 2 ); assert ( "Missing exception" == nullptr ); }
|
|
catch ( const invalid_argument & e ) { }
|
|
catch ( ... ) { assert ( "Invalid exception" == nullptr ); }
|
|
try { t . FindWay ( "Prague", "Chicago", 0 ); assert ( "Missing exception" == nullptr ); }
|
|
catch ( const invalid_argument & e ) { }
|
|
catch ( ... ) { assert ( "Invalid exception" == nullptr ); }
|
|
|
|
t . Add ( "Dallas", "Atlanta", 150, 30 )
|
|
. Add ( "Berlin", "Helsinki", 1080, 2560 )
|
|
. Add ( "Chicago", "Frankfurt", 50, 0 )
|
|
. Add ( "Helsinki", "Vienna", 3200, 3 )
|
|
. Add ( "Chicago", "London", 10, 12 )
|
|
. Add ( "London", "Atlanta", 20, 40 )
|
|
. Add ( "Vienna", "Atlanta", 10, 50 )
|
|
. Add ( "Prague", "Vienna", 1, 6 )
|
|
. Add ( "Berlin", "Helsinki", 265, 265 )
|
|
. Add ( "Berlin", "London", 259, 0 ) . Optimize ( );
|
|
|
|
assert ( t . FindWay ( "Prague", "Frankfurt", 0 ) == 0 );
|
|
assert ( t . FindWay ( "Prague", "Atlanta", 0 ) == 40 );
|
|
assert ( t . FindWay ( "Prague", "Atlanta", 10 ) == 50 );
|
|
|
|
std::cout << "success!\n";
|
|
return EXIT_SUCCESS;
|
|
}
|
|
#endif /* __PROGTEST__ */ |