SRM479 Div1 Medium

500

safety の値を2分探索しながらダイクストラする。
ところどころ signed int に収まらないことに注意。

問題文が長いし、どこか見落としそう。
UVaみたいな問題だから好きになれない。

struct E {
  int src, dst;
  lli F, T, P;
};
const int N = 500;
vector<E> g[N];

lli calc_next(E e, lli curr_time)
{
  lli a = curr_time - e.F;
  if (a <= 0) return e.F + e.T;
  lli b = (a / e.P) + (bool)(a % e.P);
  lli c = b * e.P;
  return e.F + c + e.T;
}

bool sssp(int n, lli limit, lli safety)
{
  priority_queue< pair<lli, lli> > q;
  static lli cost[N];
  fill(cost, cost + N, (1LL << 60));

  for (q.push(make_pair(0, 0)); q.size(); ) {
    lli curr = q.top().second;
    lli time = -q.top().first;
    q.pop();
    each (e, g[curr]) {
      lli next = calc_next(*e, time + (curr ? safety : 1));
      if (cost[e->dst] > next) {
        cost[e->dst] = next;
        q.push(make_pair(-next, e->dst));
      }
    }
  }
  return cost[n - 1] <= limit;
}

class TheAirTripDivOne {
public:
  int find(int n, vector <string> fs, int time)
  {
    fill(g, g + N, vector<E>());

    string s = accumulate(fs.begin(), fs.end(), string(""));
    replace(s.begin(), s.end(), ',', ' ');
    istringstream iss(s);
    for (E e; iss >> e.src >> e.dst >> e.F >> e.T >> e.P; ) {
      --e.src;
      --e.dst;
      g[e.src].push_back(e);
    }

    lli small = 1, large = time + 1;
    while (small + 1 < large) {
      lli mid = (small + large) / 2;
      if (!sssp(n, time, mid)) large = mid;
      else small = mid;
    }
    return sssp(n, time, small) ? small : -1;
  }
};