Submission #654094

#	Time	Username	Problem	Language	Result	Execution time	Memory
654094		tvladm2009	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	338 ms	29136 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll

const int N = (int) 1e5 + 7;
const int INF = (ll) 1e18;
int cnt[N];
vector<int> adj[N];
ll dist[N], minU[N], minV[N];
bool vis[N];
int n, m, s, t, u, v;

struct Edge {
  int to;
  int cost;
};

vector<Edge> g[N];

void dijkstra(int start, vector<ll> &dist) {
  for (int i = 1; i <= n; i++) {
    dist[i] = INF;
    vis[i] = 0;
  }
  priority_queue<pair<int, int>> pq;
  dist[start] = 0;
  pq.push({0, start});
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    if (vis[u] == 1) {
      continue;
    }
    vis[u] = 1;
    for (auto &edg : g[u]) {
      int v = edg.to, relax = edg.cost;
      if (dist[u] + relax < dist[v]) {
        dist[v] = dist[u] + relax;
        pq.push({-dist[v], v});
      }
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  cin >> n >> m >> s >> t >> u >> v;
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    g[x].push_back({y, z});
    g[y].push_back({x, z});
  }
  vector<ll> distS(n + 1), distT(n + 1), distU(n + 1), distV(n + 1);
  dijkstra(s, distS);
  dijkstra(t, distT);
  dijkstra(u, distU);
  dijkstra(v, distV);

  for (int u = 1; u <= n; u++) {
    for (auto &edg : g[u]) {
      if (distS[u] + edg.cost + distT[edg.to] == distS[t]) {
        adj[u].push_back(edg.to);
        cnt[edg.to]++;
      }
    }
  }
  queue<int> q;
  for (int i = 1; i <= n; i++) {
    if (cnt[i] == 0) {
      q.push(i);
    }
  }
  vector<int> topsort;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    topsort.push_back(u);
    for (auto &v : adj[u]) {
      cnt[v]--;
      if (cnt[v] == 0) {
        q.push(v);
      }
    }
  }
  reverse(topsort.begin(), topsort.end());

  ll ret = INF;
  for (auto &u : topsort) {
    minU[u] = distU[u];
    minV[u] = distV[u];
    for (auto &v : adj[u]) {
      minU[u] = min(minU[u], minU[v]);
      minV[u] = min(minV[u], minV[v]);
    }
    ret = min({ret, distU[u] + minV[u], distV[u] + minU[u]});
  }
  cout << ret;
  return 0;
}

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