Submission #1166633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166633		Zero_OP	Olympic Bus (JOI20_ho_t4)	C++20	11 / 100	1095 ms	2744 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r) - 1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define sum_of(v) accumulate(all(v), 0ll)
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vl = vector<ll>;
using vd = vector<db>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

struct edge{
      int u, v, c, d;
      edge(int u, int v, int c, int d) : u(u), v(v), c(c), d(d) {}
};

const ll inf = 1e18;

vl dijkstra(int s, vector<vi>& adj, vector<edge>& edges, int bl){
      int N = sz(adj);
      vl d(N, inf);

      d[s] = 0;
      priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
      pq.push(mp(d[s], s));

      while(!pq.empty()){
            ll dist; int u;
            tie(dist, u) = pq.top(); pq.pop();
            if(d[u] != dist) continue;
            for(auto id : adj[u]) if(id != bl){
                  int v = edges[id].v ^ edges[id].u ^ u;
                  if(minimize(d[v], d[u] + edges[id].d)){
                        pq.push(mp(d[v], v));
                  }
            }
      }
      return d;
}

vl solve(int N, int M, vector<vi>& adj, vector<vi>& radj, vector<edge>& edges, int S, int T){
      vl result(M+1, inf);
      vl dS = dijkstra(S, adj, edges, -1);
      vl dT = dijkstra(T, radj, edges, -1);

      vi par(N, -1);
      FOR(i, 0, N){
            for(auto id : adj[i]){
                  int j = edges[id].u ^ edges[id].v ^ i;
                  if(dS[j] == dS[i] + edges[id].d){
                        par[j] = id;
                  }
            }
      }

      int u = T;
      vb on(M);
      result[M] = dS[T];

      while(par[u] != -1){
            int id = par[u];
            int pr = edges[id].u ^ edges[id].v ^ u;
            on[id] = true;
            u = pr;
      }

      FOR(i, 0, M){
            if(!on[i]){
                  minimize(result[i], min(result[M], dS[edges[i].v] + dT[edges[i].u] + edges[i].d));
            } else{
                  int u = edges[i].u, v = edges[i].v;
                  edges.pb(edge(v, u, edges[i].c, edges[i].d));
                  adj[v].pb(sz(edges)-1);

                  minimize(result[i], dijkstra(S, adj, edges, i)[T]);

                  edges.pop_back();
                  adj[v].pop_back();
            }
      }

      return result;
}

signed main(){
      setIO();

      int N, M;
      cin >> N >> M;

      vector<edge> edges;
      vector<vi> adj(N), radj(N);
      FOR(i, 0, M){
            int u, v, c, d;
            cin >> u >> v >> d >> c;
            --u, --v;
            edges.pb(edge(u, v, c, d));
            adj[u].pb(i);
            radj[v].pb(i);
      }

      vl F = solve(N, M, adj, radj, edges, 0, N-1);
      vl G = solve(N, M, adj, radj, edges, N-1, 0);

      ll ans = inf;
      FOR(i, 0, M+1) {
            minimize(ans, F[i] + G[i] + (i < M ? edges[i].c : 0));
//            cout << dbg(F[i]) << dbg(G[i]) << '\n';
      }
      if(ans == inf) ans = -1;
      cout << ans << '\n';

      return 0;
}

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