Submission #846905

#	Time	Username	Problem	Language	Result	Execution time	Memory
846905		ind1v	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	399 ms	29388 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

int n, m;
int a, b, c, d;
vector<array<int, 3>> g[100005];
int u[200005];
int v[200005];
int w[200005];
long long da[100005];
long long db[100005];
bool ok[200005];
long long dd[100005][3];

void dijkstra_a() {
  memset(da, 0x3f, sizeof(da));
  da[a] = 0;
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  pq.push(make_pair(da[a], a));
  while (!pq.empty()) {
    long long cd = pq.top().first;
    int node = pq.top().second;
    pq.pop();
    if (cd != da[node]) {
      continue;
    }
    for (int i = 0; i < (int) g[node].size(); i++) {
      int nxt = g[node][i][0];
      int wt = g[node][i][1];
      if (da[nxt] > da[node] + wt) {
        da[nxt] = da[node] + wt;
        pq.push(make_pair(da[nxt], nxt));
      }
    }
  }
}

void dijkstra_b() {
  memset(db, 0x3f, sizeof(db));
  db[b] = 0;
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  pq.push(make_pair(db[b], b));
  while (!pq.empty()) {
    long long cd = pq.top().first;
    int node = pq.top().second;
    pq.pop();
    if (cd != db[node]) {
      continue;
    }
    for (int i = 0; i < (int) g[node].size(); i++) {
      int nxt = g[node][i][0];
      int wt = g[node][i][1];
      if (db[nxt] > db[node] + wt) {
        db[nxt] = db[node] + wt;
        pq.push(make_pair(db[nxt], nxt));
      }
    }
  }
}

long long dijkstra(int src, int dst) {
  memset(dd, 0x3f, sizeof(dd));
  dd[src][0] = 0;
  priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>, greater<pair<long long, pair<int, int>>>> pq;
  pq.push(make_pair(dd[src][0], make_pair(src, 0)));
  while (!pq.empty()) {
    long long cd = pq.top().first;
    int node = pq.top().second.first;
    int state = pq.top().second.second;
    pq.pop();
    if (cd != dd[node][state]) {
      continue;
    }
    for (int i = 0; i < (int) g[node].size(); i++) {
      int nxt = g[node][i][0];
      int wt = g[node][i][1];
      int eid = g[node][i][2];
      if (state <= 0) {
        if (dd[nxt][0] > cd + wt) {
          dd[nxt][0] = cd + wt;
          pq.push(make_pair(dd[nxt][0], make_pair(nxt, 0)));
        }
      }
      if (state <= 1) {
        if (ok[eid] && da[nxt] == da[node] + wt && dd[nxt][1] > cd) {
          dd[nxt][1] = cd;
          pq.push(make_pair(dd[nxt][1], make_pair(nxt, 1)));
        }
      }
      if (state <= 2) {
        if (dd[nxt][2] > cd + wt) {
          dd[nxt][2] = cd + wt;
          pq.push(make_pair(dd[nxt][2], make_pair(nxt, 2)));
        }
      }
    }
  }
  return min(dd[dst][0], min(dd[dst][1], dd[dst][2]));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  cin >> a >> b >> c >> d;
  for (int i = 1; i <= m; i++) {
    cin >> u[i] >> v[i] >> w[i];
    g[u[i]].push_back(array<int, 3>{v[i], w[i], i});
    g[v[i]].push_back(array<int, 3>{u[i], w[i], i});
  }
  dijkstra_a();
  dijkstra_b();
  for (int i = 1; i <= m; i++) {
    ok[i] |= (da[u[i]] + w[i] + db[v[i]] == da[b]);
    ok[i] |= (da[v[i]] + w[i] + db[u[i]] == da[b]);
  }
  cout << min(dijkstra(c, d), dijkstra(d, c));
  return 0;
}

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