Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

很OOP的代碼

Posted by miklcct at 2011-08-03 14:10:07 on Problem 1158
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator