Submission #98594

#	Time	Username	Problem	Language	Result	Execution time	Memory
98594		WLZ	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	779 ms	22024 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const long long INF = (long long) 1e18;

template<typename T>
struct edge {
  int from, to;
  T cost;
};

void dijkstra(int s, vector<long long>& dist, const vector< vector< edge<long long> > >& g) {
  priority_queue< pair<long long, int>, vector< pair<long long, int> >, greater< pair<long long, int> > > pq;
  pq.push({0, s});
  dist.assign((int) g.size(), INF);
  dist[s] = 0;
  while (!pq.empty()) {
    long long d = pq.top().first;
    int u = pq.top().second;
    pq.pop();
    if (d > dist[u]) {
      continue;
    }
    for (auto& v : g[u]) {
      if (d + v.cost < dist[v.to]) {
        dist[v.to] = d + v.cost;
        pq.push({dist[v.to], v.to});
      }
    }
  }
}

void calc_dp(int s, const vector<long long>& dist2, const vector< vector< edge<long long> > >& g, vector<long long>& dp) {
  dp.assign((int) g.size(), INF);
  dp[s] = dist2[s];
  vector<long long> dist((int) g.size(), INF);
  dist[s] = 0;
  priority_queue< pair<long long, int>, vector< pair<long long, int> >, greater< pair<long long, int> > > pq;
  pq.push({0, s});
  while (!pq.empty()) {
    long long d = pq.top().first;
    int u = pq.top().second;
    pq.pop();
    if (d > dist[u]) {
      continue;
    }
    for (auto& v : g[u]) {
      if (d + v.cost < dist[v.to]) {
        dist[v.to] = d + v.cost;
        pq.push({dist[v.to], v.to});
        dp[v.to] = min({dp[v.to], dp[u], dist2[v.to]});
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, s, t, u, v;
  cin >> n >> m >> s >> t >> u >> v;
  vector< vector< edge<long long> > > g(n + 1);
  for (int i = 0; i < m; i++) {
    int a, b;
    long long c;
    cin >> a >> b >> c;
    g[a].push_back({a, b, c});
    g[b].push_back({b, a, c});
  }
  vector<long long> dist1, dist2, dist3, dist4;
  dijkstra(u, dist1, g);
  dijkstra(v, dist2, g);
  dijkstra(s, dist3, g);
  dijkstra(t, dist4, g);
  vector<long long> dp1, dp2;
  calc_dp(s, dist2, g, dp1);
  calc_dp(t, dist2, g, dp2);
  long long ans = INF;
  for (int i = 1; i <= n; i++) {
    if (dist3[i] + dist4[i] == dist3[t]) {
      ans = min(ans, dist1[i] + min(dp1[i], dp2[i]));
    }
  }
  cout << min(ans, dist1[v]) << '\n';
  return 0;
}

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