Submission #1060118

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

bool chmin(long long &a, long long b) { if (a > b) { a = b; return true; } else return false; }
bool chmax(long long &a, long long b) { if (a < b) { a = b; return true; } else return false; }

typedef pair<int,int> pint;

int n, s;
long long l[510], r[510];
long long w[510][510];
const long long INF = 1LL<<59;

long long dp[510];

long long rec(int v) {
  if (dp[v] != -1) return dp[v];
  long long res = 0;
  for (int nv = 1; nv < n; ++nv) {
    if (nv == v) continue;
    long long arrive = r[v] + w[v][nv];
    if (r[nv] <= arrive) continue;
    chmax(res, rec(nv) + (r[nv] - max(arrive, l[nv])));
  }
  //cout << v << ": " << res << endl;
  return dp[v] = res;
}


long long solve() {
  memset(dp, -1, sizeof(dp));
  return rec(0);
}


int main() {
  while (cin >> n >> s) {
    for (int i = 0; i < n; ++i) cin >> l[i+1] >> r[i+1];
    l[0] = r[0] = 0;
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> w[i+1][j+1];
    for (int i = 0; i < n; ++i) w[0][i+1] = w[s][i+1], w[i+1][0] = INF;
    w[0][0] = 0;
    ++n;

    // w[i][i] = 0 is guaranteed
    for (int k = 0; k < n; ++k)
      for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      chmin(w[i][j], w[i][k] + w[k][j]);
    cout << solve() << endl;
  }
}

Submission Info

Judge Result