Submission #706188

#	Time	Username	Problem	Language	Result	Execution time	Memory
706188		cig32	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1063 ms	11884 KiB

ho_t4

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int dist1[232][232];
int distn[232][232];
int rev1[232][232];
int revn[232][232];
int refer;
bool cmp5(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y) {
  return revn[refer][x.first.first] + x.first.second < revn[refer][y.first.first] + y.first.second;
}
bool cmp6(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y) {
  return rev1[refer][x.first.first] + x.first.second < rev1[refer][y.first.first] + y.first.second;
}

mt19937_64 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  return uniform_int_distribution<int>(x, y)(rng);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  pair<pair<int,int>,pair<int,int> > e[m+1];
  for(int i=1; i<=m; i++) { // O(m)
    cin >> e[i].first.first >> e[i].first.second >> e[i].second.first >> e[i].second.second;
  }
  for(int i=0; i<=n; i++) { // O(n^2)
    for(int j=0; j<=n; j++) {
      dist1[i][j] = distn[i][j] = rev1[i][j] = revn[i][j] = 1e18;
    }
    dist1[i][1] = 0;
    distn[i][n] = 0;
    rev1[i][1] = 0;
    revn[i][n] = 0;
  }
  for(int b=0; b<=n; b++) {
    int temp[n+1][n+1];
    vector<pair<int, int> > adj[n+1], rev[n+1];
    for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) temp[i][j] = 1e18;
    for(int i=1; i<=m; i++) {
      if(e[i].first.first == b || e[i].first.second == b) continue;
      temp[e[i].first.first][e[i].first.second] = min(temp[e[i].first.first][e[i].first.second], e[i].second.first);
    }
    for(int i=1; i<=n; i++) {
      for(int j=1; j<=n; j++) {
        if(temp[i][j] <= 1e16) adj[i].push_back({j, temp[i][j]});
      }
    }
    for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) temp[i][j] = 1e18;
    for(int i=1; i<=m; i++) {
      if(e[i].first.first == b || e[i].first.second == b) continue;
      temp[e[i].first.second][e[i].first.first] = min(temp[e[i].first.second][e[i].first.first], e[i].second.first);
    }
    for(int i=1; i<=n; i++) {
      for(int j=1; j<=n; j++) {
        if(temp[i][j] <= 1e16) rev[i].push_back({j, temp[i][j]});
      }
    }
    bool vis[n+1];
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
    pq.push({dist1[b][1], 1});
    for(int i=1; i<=n; i++) vis[i] = 0;
    while(pq.size()) {
      pair<int,int> t = pq.top(); pq.pop();
      if(!vis[t.second]) {
        vis[t.second] = 1;
        for(pair<int, int> x: adj[t.second]) {
          if(!vis[x.first] && dist1[b][x.first] > dist1[b][t.second]+x.second) {
            dist1[b][x.first] = dist1[b][t.second]+x.second;
            pq.push({dist1[b][x.first], x.first});
          }
        }
      }
    }
    pq.push({distn[b][n], n});
    for(int i=1; i<=n; i++) vis[i] = 0;
    while(pq.size()) {
      pair<int,int> t = pq.top(); pq.pop();
      if(!vis[t.second]) {
        vis[t.second] = 1;
        for(pair<int, int> x: adj[t.second]) {
          if(!vis[x.first] && distn[b][x.first] > distn[b][t.second]+x.second) {
            distn[b][x.first] = distn[b][t.second]+x.second;
            pq.push({distn[b][x.first], x.first});
          }
        }
      }
    }
    pq.push({rev1[b][1], 1});
    for(int i=1; i<=n; i++) vis[i] = 0;
    while(pq.size()) {
      pair<int,int> t = pq.top(); pq.pop();
      if(!vis[t.second]) {
        vis[t.second] = 1;
        for(pair<int, int> x: rev[t.second]) {
          if(!vis[x.first] && rev1[b][x.first] > rev1[b][t.second]+x.second) {
            rev1[b][x.first] = rev1[b][t.second]+x.second;
            pq.push({rev1[b][x.first], x.first});
          }
        }
      }
    }
    pq.push({revn[b][n], n});
    for(int i=1; i<=n; i++) vis[i] = 0;
    while(pq.size()) {
      pair<int,int> t = pq.top(); pq.pop();
      if(!vis[t.second]) {
        vis[t.second] = 1;
        for(pair<int, int> x: rev[t.second]) {
          if(!vis[x.first] && revn[b][x.first] > revn[b][t.second]+x.second) {
            revn[b][x.first] = revn[b][t.second]+x.second;
            pq.push({revn[b][x.first], x.first});
          }
        }
      }
    }
  }
  int ans = dist1[0][n] + distn[0][1];
  vector<pair<int,int> > adj[n+1], rev[n+1];
  vector<int> adj_id[n+1];
  for(int i=1; i<=m; i++) { // O(m)
    adj_id[e[i].first.first].push_back(i);
    adj[e[i].first.first].push_back({e[i].first.second, e[i].second.first});
    rev[e[i].first.second].push_back({e[i].first.first, e[i].second.first});
  }
  int cnt[n+1][n+1];
  for(int i=0; i<=n; i++) { // O(n^2)
    for(int j=0; j<=n; j++) {
      cnt[i][j] = 0;
    }
  }
  for(int i=1; i<=m; i++) { // O(m)
    cnt[e[i].first.first][e[i].first.second]++;
  }
  int opt1[n+1], opt2[n+1], opt3[n+1], opt4[n+1];
  for(int i=1; i<=n; i++) { // O(m)
    opt1[i] = opt2[i] = opt3[i] = opt4[i] = 1e18;
    for(pair<int, int> x: adj[i]) {
      opt1[i] = min(opt1[i], x.second + revn[i][x.first]);
      opt3[i] = min(opt3[i], x.second + rev1[i][x.first]);
    }
    for(pair<int, int> x: rev[i]) {
      opt2[i] = min(opt2[i], dist1[i][x.first] + x.second);
      opt4[i] = min(opt4[i], distn[i][x.first] + x.second);
    }
  }
  vector<pair<pair<int,int>, int> > opt5[n+1], opt6[n+1];
  for(int i=1; i<=n; i++) { // O(m log m)
    for(int j=0; j<adj[i].size(); j++) {
      opt5[i].push_back({adj[i][j], adj_id[i][j]});
    }
    refer = i;
    sort(opt5[i].begin(), opt5[i].end(), cmp5);
    for(int j=0; j<adj[i].size(); j++) {
      opt6[i].push_back({adj[i][j], adj_id[i][j]});
    }
    sort(opt6[i].begin(), opt6[i].end(), cmp6);
  }
  for(int i=1; i<=m; i++) { // O(m)
    int forward, backward;
    forward = dist1[e[i].first.first][e[i].first.second] + e[i].second.first;
    int mi = (e[i].first.first == n ? 0 : 1e18);
    mi = min(mi, opt1[e[i].first.first]);
    forward += mi;
    forward = min(forward, dist1[e[i].first.first][n]);
    
    int pt1 = (e[i].first.first == 1 ? 0 : 1e18);
    int pt2 = (e[i].first.first == n ? 0 : 1e18);
    pt1 = min(pt1, opt2[e[i].first.first]);
    for(pair<pair<int,int>, int> x: opt5[e[i].first.first]) {
      if(x.second == i) {
        continue;
      }
      pt2 = min(pt2, revn[e[i].first.first][x.first.first] + x.first.second);
      break;
    }
    forward = min(forward, pt1 + pt2);
    backward = distn[e[i].first.first][e[i].first.second] + e[i].second.first;
    mi = (e[i].first.first == 1 ? 0 : 1e18);
    mi = min(mi, opt3[e[i].first.first]);
    backward += mi;
    backward = min(backward, distn[e[i].first.first][1]);
    pt1 = (e[i].first.first == n ? 0 : 1e18);
    pt2 = (e[i].first.first == 1 ? 0 : 1e18);
    pt1 = min(pt1, opt4[e[i].first.first]);
    for(pair<pair<int,int>, int> x: opt6[e[i].first.first]) {
      if(x.second == i) {
        continue;
      }
      pt2 = min(pt2, rev1[e[i].first.first][x.first.first] + x.first.second);
      break;
    }
    backward = min(backward, pt1 + pt2);
    ans = min(ans, forward + backward + e[i].second.second);
    //cout << "flip pair<pair<int,int>,pair<int,int> > " << i << ": " << forward << " + " << backward << " + " << e[i].second.second << " = " << forward + backward + e[i].second.second << "\n";
  }
  cout << (ans <= 1e12 ? ans : -1) << "\n";
}

Compilation message (stderr)

ho_t4.cpp: In function 'int32_t main()':
ho_t4.cpp:152:19: 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]
  152 |     for(int j=0; j<adj[i].size(); j++) {
      |                  ~^~~~~~~~~~~~~~
ho_t4.cpp:157:19: 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]
  157 |     for(int j=0; j<adj[i].size(); j++) {
      |                  ~^~~~~~~~~~~~~~

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