Submission #1166651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166651		Zero_OP	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	592 ms	327680 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 int inf = 2e9 + 9;

pair<vi, vi> dijkstra_with_trace(int s, vector<vi>& adj, vector<edge>& edges, int t){
      int N = sz(adj);
      vi d(N, inf);

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

      vb vis(N);
      vi par(N, -1);
      while(!pq.empty()){
            int dist; int u;
            tie(dist, u) = pq.top(); pq.pop();
            if(vis[u]) continue;
            vis[u] = true;
            for(auto id : adj[u]){
                  int v = edges[id].v ^ edges[id].u ^ u;
                  if(minimize(d[v], d[u] + edges[id].d)){
                        par[v] = id;
                        pq.push(mp(d[v], v));
                  }
            }
      }

      vi p;
      while(s != t){
           p.pb(par[t]);
           int id = par[t];
           t ^= edges[id].u ^ edges[id].v;
      }

      return mp(d, p);
}

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

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

      vb vis(N);
      while(!pq.empty()){
            int dist; int u;
            tie(dist, u) = pq.top(); pq.pop();
            if(vis[u]) continue;
            vis[u] = true;
            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;
}

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

      vi par(N, -1);
      FOR(i, 0, N) if(dS[i] != inf){
            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;
                  }
            }
      }

      vb on(M);
      for(auto id : p) on[id] = true;
      result[M] = dS[T];

      int cnt = 0;
      FOR(i, 0, M){
            if(!on[i]){
                  if(dS[edges[i].v] == inf || dT[edges[i].u] == inf) continue;
                  minimize(result[i], min(result[M], dS[edges[i].v] + dT[edges[i].u] + edges[i].d));
            } else{
                  ++cnt;
                  assert(cnt < N);
                  int u = edges[i].u, v = edges[i].v;
                  assert(edges[i].d >= 0);

                  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);
      }

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

      int ans = inf;
      FOR(i, 0, M+1) {
            if(F[i] == inf || G[i] == inf) continue;
            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: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63