Submission #733604

#	Time	Username	Problem	Language	Result	Execution time	Memory
733604		asdfgrace	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	445 ms	32708 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);
    ds = dijkstra(s, 0);
    du = dijkstra(u, 1);
    dv = dijkstra(v, 1);
    ans = du[v];
    
    dpu.resize(n);
    dpv.resize(n);
    bfs(s, t, 0);
    bfs(t, s, 1);
    
    cout << ans << '\n';
  }
  
  void bfs(i64 start, i64 end, int order) {
    fill(dpu.begin(), dpu.end(), INF);
    fill(dpv.begin(), dpv.end(), INF);
    queue<i64> q;
    vector<bool> visited(n, false);
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
      i64 node = q.front();
      q.pop();
      dpu[node] = du[node];
      dpv[node] = dv[node];
      for (auto prev : sp[order][node]) {
        dpu[node] = min(dpu[node], dpu[prev]);
        dpv[node] = min(dpv[node], dpv[prev]);
      }
      for (auto next : sp[order^1][node]) {
        if (!visited[next]) {
          visited[next] = true;
          q.push(next);
        }
      }
    }
    ans = min(ans, dpu[end] + dpv[end]);
  }
  
  vector<i64> dijkstra(i64 start, int run) {
    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]) {
          if (run == 0) {
            sp[0][next].push_back(node);
            sp[1][node].push_back(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, int)':
commuter_pass.cpp:79:11: warning: unused variable 'dist' [-Wunused-variable]
   79 |       i64 dist = q.top().first;
      |           ^~~~

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