Submission #1158784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158784		Zero_OP	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	1096 ms	65868 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 all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

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

#define dbg(x) "[" #x " = " << (x) << "]"
#define readFile(task) freopen(task, "r", stdin)
#define writeFile(task) freopen(task, "w", stdout)

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 vstr = vector<string>;
using vl = vector<ll>;
using vd = vector<double>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      readFile("task.inp");
      writeFile("task.out");
#endif //LOCAL
}

int main(){
      setIO();

      int N, M;
      cin >> N >> M;
      vector<vi> adj(N), adj_rev(N);
      vi U(M), V(M), C(M), D(M);
      FOR(i, 0, M){
            int u, v, c, d;
            cin >> u >> v >> c >> d;
            --u, --v;

            tie(U[i], V[i], C[i], D[i]) = mt(u, v, c, d);
            adj[u].pb(i);
            adj_rev[v].pb(i);
      }

      const int inf = 2e9;
      vector<vi> dp(N, vi(M+1, inf));

      using node = tuple<int, int, int>;
      priority_queue<node, vector<node>, greater<node>> pq;

      dp[0][M] = 0;
      pq.push(mt(0, 0, M));

      int dist, u, idx;
      while(!pq.empty()){
            tie(dist, u, idx) = pq.top(); pq.pop();
            if(dp[u][idx] != dist) continue;

            for(auto id : adj[u]) if(id != idx){
                  int v = V[id], w = C[id];
                  if(dp[v][idx] > dist + w){
                        dp[v][idx] = dist + w;
                        pq.push(mt(dp[v][idx], v, idx));
                  }
            }

            if(idx == M){
                  for(auto id : adj_rev[u]){
                        int v = U[id], w = C[id] + D[id];
                        if(dp[v][id] > dist + w){
                              dp[v][id] = dist + w;
                              pq.push(mt(dp[v][id], v, id));
                        }
                  }
            } else{
                  if(u == V[idx]){
                        //(V[idx] -> U[idx]) with cost C[idx]
                        int v = U[idx], w = C[idx];
                        if(dp[v][idx] > dist + w){
                              dp[v][idx] = dist + w;
                              pq.push(mt(dp[v][idx], v, idx));
                        }
                  }
            }
      }

      vector<vi> f(N, vi(M+1, inf));

      FOR(i, 0, M+1){
            if(dp[N-1][i] != inf){
                  f[N-1][i] = dp[N-1][i];
                  pq.push(mt(f[N-1][i], N-1, i));
            }
      }

      while(!pq.empty()){
            tie(dist, u, idx) = pq.top(); pq.pop();
            if(u == 0){
                  cout << dist << '\n';
                  return 0;
            }

            if(dist != f[u][idx]) continue;

            for(auto id : adj[u]) if(id != idx){
                  int v = V[id], w = C[id];
                  if(f[v][idx] > dist + w){
                        f[v][idx] = dist + w;
                        pq.push(mt(f[v][idx], v, idx));
                  }
            }

            if(idx == M){
                  for(auto id : adj_rev[u]){
                        int v = U[id], w = C[id] + D[id];
                        if(f[v][id] > dist + w){
                              f[v][id] = dist + w;
                              pq.push(mt(f[v][id], v, id));
                        }
                  }
            } else{
                  if(u == V[idx]){
                        //(V[idx] -> U[idx]) with cost C[idx]
                        int v = U[idx], w = C[idx];
                        if(f[v][idx] > dist + w){
                              f[v][idx] = dist + w;
                              pq.push(mt(f[v][idx], v, idx));
                        }
                  }
            }
      }

      cout << -1 << '\n';

      return 0;
}

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