Submission #733620

#	Time	Username	Problem	Language	Result	Execution time	Memory
733620		asdfgrace	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	473 ms	36104 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << endl)
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
typedef int64_t i64;
const i64 INF = 1e18; //1000000007; //998244353;

struct S {
  i64 n, m, s, t, u, v, ans;
  vector<vector<pair<i64, i64>>> edges;
  vector<i64> ds, du, dv, dpu, dpv;
  array<vector<vector<i64>>, 2> sp;

  void run() {
    cin >> n >> m >> s >> t >> u >> v;
    --s; --t; --u; --v;
    edges.resize(n);
    for (int i = 0; i < m; ++i) {
      i64 a, b, c;
      cin >> a >> b >> c;
      --a; --b;
      edges[a].push_back({b, c});
      edges[b].push_back({a, c});
    }
    
    sp[0].resize(n);
    sp[1].resize(n);
    du = dijkstra(u); PAR(du);
    dv = dijkstra(v); PAR(dv);
    ans = du[v]; PV(ans);
    
    dpu.resize(n);
    dpv.resize(n);
    dijkstra2(s, t); PAR(dpu); PAR(dpv);
    dijkstra2(t, s); PAR(dpu); PAR(dpv);
    
    cout << ans << '\n';
  }
  
  void dijkstra2(i64 start, i64 end) {
    fill(dpu.begin(), dpu.end(), INF);
    fill(dpv.begin(), dpv.end(), INF);
    
    vector<i64> d(n, INF);
    d[start] = 0;
    vector<bool> visited(n, false);
    priority_queue<array<i64, 3>> q;
    q.push({0, start, 0});
    
    while (!q.empty()) {
      i64 dist = -q.top()[0];
      i64 node = q.top()[1];
      i64 prev = q.top()[2];
      q.pop();
      if (!visited[node]) {
        visited[node] = true;
        d[node] = dist;
        dpu[node] = min(du[node], dpu[prev]);
        dpv[node] = min(dv[node], dpv[prev]);
        for (auto [next, wt] : edges[node]) {
          q.push({-d[node] - wt, next, node});
        }
      } else if (dist == d[node]) {
        if (min(du[node], dpu[prev]) + min(dv[node], dpv[prev])
          <= dpu[node] + dpv[node]) {
          dpu[node] = min(du[node], dpu[prev]);
          dpv[node] = min(dv[node], dpv[prev]);
        }
      }
    }
    ans = min(ans, dpu[end] + dpv[end]);
  }
  
  vector<i64> dijkstra(i64 start) {
    vector<i64> d(n, INF);
    d[start] = 0;
    vector<bool> visited(n, false);
    priority_queue<pair<i64, i64>> q;
    q.push({0, start});
    
    while (!q.empty()) {
      i64 dist = q.top().first;
      i64 node = q.top().second;
      q.pop();
      if (visited[node]) continue;
      
      visited[node] = true;
      for (auto [next, wt] : edges[node]) {
        if (d[node] + wt <= d[next]) {
          d[next] = d[node] + wt;
          q.push({-d[node] - wt, next});
        }
      }
    }
    
    return d;
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  auto sol = make_unique<S>();
  sol->run();
}

Compilation message (stderr)

commuter_pass.cpp: In member function 'std::vector<long int> S::dijkstra(i64)':
commuter_pass.cpp:86:11: warning: unused variable 'dist' [-Wunused-variable]
   86 |       i64 dist = q.top().first;
      |           ^~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45