Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
很OOP的代碼In Reply To:贴AC代码,SPFA过的~ Posted by:yzhw at 2010-05-29 01:43:52 #include <algorithm> #include <climits> #include <iostream> #include <map> #include <queue> using namespace std; typedef int Time; const Time impossible = INT_MIN; class Junction { public: typedef bool Colour; Junction(); static const bool blue = false; static const bool purple = true; // Return the colour and the remaining time of the light pair<Colour, Time> query(Time moment) const; // Build a road to join this and target void join(Junction *target, Time length); // Find the shortest travel time to target Time travel_time(const Junction *target) const; // Find the waiting time here to another junction, return impossible if // no-go Time waiting_time(const Junction *target, Time moment, int level = 0) const; Colour initial; Time remaining; Time durations[2]; private: struct Road { const Junction *targets[2]; Time length; bool operator<(const Road &rhs) const; }; static Road roads[]; static size_t used_roads; mutable Time time; }; int main() { ios::sync_with_stdio(false); size_t a, b; cin >> a >> b; --a; --b; size_t n, m; cin >> n >> m; Junction junctions[n]; for (Junction *p = junctions; p != junctions + n; ++p) { char c; Time r, tb, tp; cin >> c >> r >> tb >> tp; p->initial = c == 'B' ? Junction::blue : Junction::purple; p->remaining = r; p->durations[Junction::blue] = tb; p->durations[Junction::purple] = tp; } for (size_t h = 0; h < m; ++h) { size_t i, j; Time l; cin >> i >> j >> l; --i; --j; junctions[i].join(junctions + j, l); } cout << junctions[a].travel_time(junctions + b) << '\n'; } void Junction::join(Junction *target, Time length) { Road road = {{this, target}, length}; roads[used_roads++] = road; swap(road.targets[0], road.targets[1]); roads[used_roads++] = road; } Time Junction::travel_time(const Junction *target) const { sort(roads, roads + used_roads); time = 0; queue<const Junction *> q; q.push(this); while (!q.empty()) { const Junction *current = q.front(); Road reference = {{current, NULL}, 0}; pair<vector<Road>::const_iterator, vector<Road>::const_iterator> bounds = equal_range(roads, roads + used_roads, reference); for (vector<Road>::const_iterator i = bounds.first; i != bounds.second; ++i) { Time x = i->length + current->waiting_time(i->targets[1], current->time); if (x >= 0) { Time new_time = current->time + x; if (i->targets[1]->time == impossible || new_time < i->targets[1]->time) { i->targets[1]->time = new_time; q.push(i->targets[1]); } } } q.pop(); } if (target->time == impossible) return 0; return target->time; } Time Junction::waiting_time(const Junction *target, Time moment, int level) const { if (level >= 20) { return impossible; } pair<Colour, Time> data[] = {query(moment), target->query(moment)}; if (data[0].first == data[1].first) { return 0; } else { Time state_change = min(data[0].second, data[1].second); return state_change + waiting_time(target, moment + state_change, level + 1); } } pair<Junction::Colour, Time> Junction::query(Time moment) const { if (moment < remaining) { return pair<Colour, Time>(initial, remaining - moment); } Time cycle = durations[0] + durations[1]; moment -= remaining; moment %= cycle; if (moment < durations[!initial]) { return pair<Colour, Time>(!initial, durations[!initial] - moment); } else { return pair<Colour, Time>(initial, cycle - moment); } } const bool Junction::blue; const bool Junction::purple; Junction::Road Junction::roads[28000]; size_t Junction::used_roads; bool Junction::Road::operator<(const Road &rhs) const { return targets[0] < rhs.targets[0]; } Junction::Junction() : time(impossible) { } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator