Submission #1026484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026484		NeroZein	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	860 ms	2904 KiB

ho_t4

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

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

using pii = pair<int, int>;

const int N = 202;
const int INF = 2e9 + 9;

struct edge {
  int from, to, c, d;
};

int n, m;
int pe[N], pv[N];
vector<int> g[N];

vector<int> dijkstra(int src, vector<edge>& e) {
  vector<int> dist(n + 1, INF);
  dist[src] = 0; 
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  pq.push({0, src});
  while (!pq.empty()) {
    auto [c, v] = pq.top();
    pq.pop();
    if (c != dist[v]) {
      continue; 
    }
    for (int i : g[v]) {
      int u = v ^ e[i].from ^ e[i].to;
      if (c + e[i].c < dist[u]) {
        pe[u] = i;
        pv[u] = v;
        dist[u] = c + e[i].c;
        pq.push({dist[u], u});
      }
    }
  }
  return dist;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  vector<edge> e(m);
  for (int i = 0; i < m; ++i) {
    int u, v, c, d;
    cin >> u >> v >> c >> d;
    e[i] = {u, v, c, d}; 
    g[u].push_back(i); 
  }
  vector<bool> marked(m);
  vector<vector<int>> dist(n + 1); 
  dist[1] = dijkstra(1, e);
  if (dist[1][n] != INF) {
    int x = n;
    while (x != 1) {
      assert(pv[x] != 0);
      marked[pe[x]] = true;
      x = pv[x]; 
    }
  }
  for (int i = 1; i <= n; ++i) {
    pe[i] = pv[i] = 0; 
  }
  dist[n] = dijkstra(n, e);
  if (dist[n][1] != INF) {
    int x = 1;
    while (x != n) {
      assert(pv[x] != 0);
      marked[pe[x]] = true;
      x = pv[x]; 
    }    
  }
  int ans = INF;
  if (dist[1][n] != INF && dist[n][1] != INF) {
    ans = dist[1][n] + dist[n][1];
  }
  for (int i = 2; i < n; ++i) {
    dist[i] = dijkstra(i, e);
  }
  for (int i = 0; i < m; ++i) {
    if (marked[i]) {
      continue; 
    }
    int u = e[i].from, v = e[i].to; 
    if (dist[1][n] != INF && dist[n][v] != INF && dist[u][1] != INF) {
      ans = min(ans, e[i].d + dist[1][n] + dist[n][v] + e[i].c + dist[u][1]);
    }
    if (dist[1][v] != INF && dist[u][n] != INF && dist[n][1] != INF) {
      ans = min(ans, e[i].d + dist[1][v] + e[i].c + dist[u][n] + dist[n][1]);
    }
    if (dist[1][v] != INF && dist[u][n] != INF && dist[n][v] != INF && dist[u][1] != INF) {
      ans = min(ans, e[i].d + dist[1][v] + e[i].c + dist[u][n] + dist[n][v] + e[i].c + dist[u][1]);
    }
  }
  for (int i = 0; i < m; ++i) {
    if (!marked[i]) {
      continue; 
    }
    int u = e[i].from, v = e[i].to;
    g[u].erase(find(g[u].begin(), g[u].end(), i));
    g[v].push_back(i);
    swap(e[i].from, e[i].to);//useless, but for the logic
    dist[1] = dijkstra(1, e); 
    dist[n] = dijkstra(n, e);
    if (dist[1][n] != INF && dist[n][1] != INF) {
      ans = min(ans, e[i].d + dist[1][n] + dist[n][1]); 
    }
    g[v].pop_back();
    g[u].push_back(i);
    swap(e[i].from, e[i].to); 
  }
  if (ans == INF) {
    ans = -1; 
  }
  cout << ans << '\n'; 
  return 0;
}

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