Submission #99098

#	Time	Username	Problem	Language	Result	Execution time	Memory
99098		WLZ	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	935 ms	32224 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(const vector< vector< edge<long long> > >& g, int s, vector<long long>& dist, vector< vector<int> >& newG) {
  dist.assign((int) g.size(), INF);
  dist[s] = 0;
  newG.assign((int) g.size(), {});
  priority_queue< pair<long long, int>, vector< pair<long long, int> >, greater< pair<long long, int> > > pq;
  vector<int> p((int) g.size(), -1);
  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});
        p[v.to] = u;
      }
    }
  }
  for (int i = 1; i < (int) g.size(); i++) {
    if (p[i] != -1) {
      newG[p[i]].push_back(i);
    }
  }
}

void calc_dp(const vector< vector<int> >& g, const vector<long long>& dist, int s, vector<long long>& dp) {
  queue<int> que;
  que.push(s);
  dp.assign((int) g.size(), INF);
  dp[s] = dist[s];
  vector<int> was((int) g.size(), 0);
  was[s] = 0;
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (auto& v : g[u]) {
      if (!was[v]) {
        que.push(v);
        dp[v] = min(dp[u], dist[v]);
        was[v] = 1;
      }
    }
  }
}

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> dist_u, dist_v, dist_s, dist_t, dp1, dp2;
  vector< vector<int> > g_s, g_t;
  dijkstra(g, u, dist_u, g_s);
  dijkstra(g, v, dist_v, g_s);
  dijkstra(g, s, dist_s, g_s);
  dijkstra(g, t, dist_t, g_t);
  calc_dp(g_s, dist_v, s, dp1);
  calc_dp(g_t, dist_v, t, dp2);
  long long ans = INF;
  for (int i = 1; i <= n; i++) {
    if (dist_s[i] + dist_t[i] == dist_s[t]) {
      ans = min(ans, dist_u[i] + min(dp1[i], dp2[i]));
    }
  }
  cout << min(ans, dist_u[v]) << '\n';
  return 0;
}

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