Submission #705669

#	Time	Username	Problem	Language	Result	Execution time	Memory
705669		cig32	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	784 ms	6988 KiB

ho_t4

#include "bits/stdc++.h"
#define int long long
using namespace std;
struct edge {
  int u, v, c, d;
};
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  edge e[m+1];
  for(int i=1; i<=m; i++) {
    cin >> e[i].u >> e[i].v >> e[i].c >> e[i].d;
  }
  int dist1[n+1][n+1], distn[n+1][n+1];
  int rev1[n+1][n+1], revn[n+1][n+1]; // b=0: nothing 
  for(int i=0; i<=n; i++) {
    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++) {
    vector<pair<int, int> > adj[n+1], rev[n+1];
    bool vis[n+1];
    for(int i=1; i<=m; i++) {
      if(e[i].u != b && e[i].v != b) {
        adj[e[i].u].push_back({e[i].v, e[i].c});
        rev[e[i].v].push_back({e[i].u, e[i].c});
      }
    }
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
    for(int i=1; i<=n; i++) pq.push({dist1[b][i], i});
    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]) {
        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});
          }
        }
      }
    }
    for(int i=1; i<=n; i++) pq.push({distn[b][i], i});
    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]) {
        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});
          }
        }
      }
    }
    for(int i=1; i<=n; i++) pq.push({rev1[b][i], i});
    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]) {
        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});
          }
        }
      }
    }
    for(int i=1; i<=n; i++) pq.push({revn[b][i], i});
    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]) {
        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];
  for(int i=1; i<=m; i++) {
    adj[e[i].u].push_back({e[i].v, e[i].c});
    adj[e[i].v].push_back({e[i].u, e[i].c});
  }
  for(int i=1; i<=m; i++) {
    int forward, backward;
    if(e[i].u > 1) {
      forward = dist1[e[i].u][e[i].v] + e[i].c;
      int mi = (e[i].u == n ? 0 : 1e18);
      for(pair<int,int> x: adj[e[i].u]) {
        mi = min(mi, x.second + revn[e[i].u][x.first]);
      }
      forward += mi;
      forward = min(forward, dist1[e[i].u][n]);
    }
    else {
      int mi = 1e18;
      for(pair<int,int> x: rev[e[i].v]) {
        mi = min(mi, x.second + dist1[e[i].v][x.first]);
      }
      forward = mi + e[i].c + e[i].d + revn[e[i].v][e[i].u];
      forward = min(forward, dist1[e[i].v][n]);
    }
    if(e[i].u < n) {
      backward = distn[e[i].u][e[i].v] + e[i].c;
      int mi = (e[i].u == 1 ? 0 : 1e18);
      for(pair<int,int> x: adj[e[i].u]) {
        mi = min(mi, x.second + rev1[e[i].u][x.first]);
      }
      backward += mi;
      backward = min(backward, distn[e[i].u][1]);
    }
    else {
      int mi = 1e18;
      for(pair<int,int> x: rev[e[i].v]) {
        mi = min(mi, x.second + revn[e[i].v][x.first]);
      }
      backward = mi + e[i].c + e[i].d + rev1[e[i].v][e[i].u];
      backward = min(backward, distn[e[i].v][1]);
    }
    ans = min(ans, forward + backward + e[i].d);
    //cout << "flip edge " << i << ": " << forward << " + " << backward << " + " << e[i].d << " = " << forward + backward + e[i].d << "\n";
  }
  cout << (ans <= 1e12 ? ans : -1) << "\n";
}

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