Submission #757830

#	Time	Username	Problem	Language	Result	Execution time	Memory
757830		taher	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	372 ms	33188 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int N = 100000;
const long long inf = 200000000000000;

long long d[4][N];
vector<array<long long, 2>> adj[N];
vector<int> adjDAG[N];
long long dp[N][4];

/*
  d[0] : Shortest distance from S
  d[1] : Shortest distance from T
  d[2] : Shortest distance from U
  d[3] : Shortest distance from V
*/

void initArrays(int n) {
  for (int i = 0; i < n; i++) {
    d[0][i] = d[1][i] = d[2][i] = d[3][i] = inf;
  }
  for (int id = 0; id < n; id++) {
    for (int j = 0; j < 4; j++) {
      dp[id][j] = -1;
    }
  }
  return ;
}

void runDijkstra(int u, int id) {
  priority_queue<array<long long, 2>, vector<array<long long, 2>>, greater<array<long long, 2>>> pQue;
  d[id][u] = 0;
  pQue.push({d[id][u], u});
  while (!pQue.empty()) {
    auto t = pQue.top();
    pQue.pop();
    if (t[0] != d[id][t[1]]) {
      continue;
    }
    for (auto x : adj[t[1]]) {
      if (d[id][x[0]] > t[0] + x[1]) {
        d[id][x[0]] = t[0] + x[1];
        pQue.push({d[id][x[0]], x[0]});
      }
    }
  }
  return ;
}

long long DP(int u, int id) {
  if (dp[u][id] != -1) {
    return dp[u][id];
  }
  long long res = d[id][u];
  for (auto x : adjDAG[u]) {
    res = min(res, DP(x, id));
  }
  return dp[u][id] = res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  initArrays(n);
  int s, t;
  cin >> s >> t;
  --s, --t;
  int u, v;
  cin >> u >> v;
  --u, --v;
  vector<array<int, 3>> edges;
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x, --y;
    adj[x].push_back({y, z});
    adj[y].push_back({x, z});
    edges.push_back({x, y, z});
  }

  runDijkstra(s, 0);
  runDijkstra(t, 1);
  runDijkstra(u, 2);
  runDijkstra(v, 3);

  long long cCost = d[0][t];

  for (int i = 0; i < m; i++) {
    int x = edges[i][0];
    int y = edges[i][1];
    int z = edges[i][2];
    if (d[0][x] + z + d[1][y] == cCost) {
      adjDAG[x].push_back(y);
    } else if (d[0][y] + z + d[1][x] == cCost) {
      adjDAG[y].push_back(x);
    }
  }

  long long res = inf;
  for (int i = 0; i < n; i++) {
    // u->i->midPoint->v
    long long uToi = d[2][i] + DP(i, 3);
    // v->i->midPoint->u
    long long vToi = d[3][i] + DP(i, 2);
    res = min(res, uToi);
    res = min(res, vToi);
  }
  res = min(res, d[2][v]);
  cout << res << '\n';
  return 0;
}

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