Submission #897843

#	Time	Username	Problem	Language	Result	Execution time	Memory
897843		avighna	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1063 ms	10568 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll N = 201, M = 50001;

ll n, m;
// first -> distance, second -> length
vector<pair<ll, ll>> dist[N][N];
vector<ll> edges_cnt[N][N];

vector<pair<ll, ll>> adj[N];
ll c[M], d[M];
pair<ll, ll> edges[M];

void insert_dist(ll i, ll j, ll d, ll l) {
  dist[i][j].push_back({d, l});
  sort(dist[i][j].begin(), dist[i][j].end());
  while (dist[i][j].size() > 2) {
    dist[i][j].pop_back();
  }
}

ll get_dist(ll u, ll v) { return dist[u][v][0].first; }

ll get_rdist(ll a, ll b, ll i) {
  // we can't use edge number i
  pair<ll, ll> p = {a, b};
  if (edges[i] != p) {
    return dist[a][b][0].first;
  }
  ll ans = 1e15;
  bool dup_exists = false;
  for (auto &e : edges_cnt[a][b]) {
    if (e == i) {
      continue;
    }
    if (c[e] == c[i]) {
      dup_exists = true;
    }
    ans = min(ans, c[e]);
  }
  for (ll i = 0; i < dist[a][b].size(); ++i) {
    if (dist[a][b][i].second != 1) {
      ans = min(ans, dist[a][b][i].first);
      continue;
    }
    if (!dup_exists && dist[a][b][i].first == c[i]) {
      continue;
    }
    ans = min(ans, dist[a][b][i].first);
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> m;
  for (ll i = 1; i <= n; ++i) {
    adj[i].clear();
  }
  for (ll i = 1; i <= n; ++i) {
    for (ll j = 1; j <= n; ++j) {
      insert_dist(i, j, 1e15, 0);
    }
  }
  for (ll i = 1; i <= n; ++i) {
    insert_dist(i, i, 0, 0);
  }
  for (ll i = 0, u, v; i < m; ++i) {
    cin >> u >> v >> c[i] >> d[i];
    adj[u].emplace_back(v, i);
    edges[i] = {u, v};
    edges_cnt[u][v].push_back(i);
    insert_dist(u, v, c[i], 1);
  }

  for (ll a = 1; a <= n; ++a) {
    for (ll b = 1; b <= n; ++b) {
      for (ll c = 1; c <= n; ++c) {
        insert_dist(a, c, dist[a][b][0].first + dist[b][c][0].first,
                    dist[a][b][0].second + dist[b][c][0].second);
      }
    }
  }

  set<ll> edges_to, edges_from;
  if (get_dist(1, n) != (ll)1e15) {
    for (ll node = 1; node != n;) {
      for (auto &nb : adj[node]) {
        if (c[nb.second] + get_dist(nb.first, n) == get_dist(node, n)) {
          edges_to.insert(nb.second);
          node = nb.first;
        }
      }
    }
  }
  if (get_dist(n, 1) != (ll)1e15) {
    for (ll node = n; node != 1;) {
      for (auto &nb : adj[node]) {
        if (c[nb.second] + get_dist(nb.first, 1) == get_dist(node, 1)) {
          edges_from.insert(nb.second);
          node = nb.first;
        }
      }
    }
  }

  ll ans = min((ll)1e15, get_dist(1, n) + get_dist(n, 1));
  for (ll i = 0; i < m; ++i) {
    ll u = edges[i].first, v = edges[i].second;
    ll _ans = d[i];
    if (edges_to.count(i)) {
      _ans += get_rdist(1, v, i) + c[i] + get_rdist(u, n, i);
    } else {
      _ans +=
          min(get_dist(1, n), get_rdist(1, v, i) + c[i] + get_rdist(u, n, i));
    }
    if (edges_from.count(i)) {
      _ans += get_rdist(n, v, i) + c[i] + get_rdist(u, 1, i);
    } else {
      _ans +=
          min(get_dist(n, 1), get_rdist(n, v, i) + c[i] + get_rdist(u, 1, i));
    }
    ans = min(ans, _ans);
  }
  if (ans == (ll)1e15) {
    ans = -1;
  }
  cout << ans << "\n";
}

Compilation message (stderr)

ho_t4.cpp: In function 'long long int get_rdist(long long int, long long int, long long int)':
ho_t4.cpp:45:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (ll i = 0; i < dist[a][b].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63