| ||||||||||
| 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