Submission #444947

#	Time	Username	Problem	Language	Result	Execution time	Memory
444947		erke	Commuter Pass (JOI18_commuter_pass)	C++11	40 / 100	442 ms	22712 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 100005;

int n, m, s, t, u, v;
vector<pair<ll,int>> adj[N];

bool minself(ll &a, ll b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void dijkstra(int start, vector<ll> &dist) {
  vector<int> vst(n + 1);
  dist.assign(n + 1, 1e15);
  dist[start] = 0;
  priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
  pq.push(make_pair(0, start));
  while (pq.size()) {
    auto i = pq.top(); pq.pop();
    if (vst[i.second]) continue;
    vst[i.second] = 1;
    for (auto &j : adj[i.second]) {
      ll comp = i.first + j.first;
      if (comp < dist[j.second]) {
        dist[j.second] = comp;
        pq.push(make_pair(comp, j.second));
      }
    }
  }
}

// S == U
namespace sub1 {
  void Main() {
    vector<ll> s_dist, v_dist, t_dist;
    dijkstra(s, s_dist);
    dijkstra(v, v_dist);
    dijkstra(t, t_dist);
    ll ans = s_dist[v];
    for (int i = 1; i <= n; i++) {
      if (s_dist[i] + t_dist[i] == s_dist[t]) {
        minself(ans, v_dist[i]);
      }
    }
    cout << ans << '\n';
  }
}

// n <= 300
namespace sub3 {
  void Main() {
    vector<vector<ll>> mat_dist(n + 1, vector<ll>(n + 1, 1e15));
    for (int i = 1; i <= n; i++) {
      mat_dist[i][i] = 0;
      for (auto &j : adj[i]) {
        mat_dist[i][j.second] = mat_dist[j.second][i] = j.first;
      }
    }
    for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      minself(mat_dist[i][j], mat_dist[i][k] + mat_dist[k][j]);
    }
    ll ans = mat_dist[u][v];
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (mat_dist[s][i] + mat_dist[i][j] + mat_dist[j][t] == mat_dist[s][t]) {
        minself(ans, mat_dist[u][i] + mat_dist[j][v]);
        minself(ans, mat_dist[u][j] + mat_dist[i][v]);
      }
    }
    cout << ans << '\n';
  }
}

// unique min path s -> t
namespace sub2 {
  void Main() {
    vector<ll> s_dist;
    dijkstra(s, s_dist);
    int tmp = t;
    while (tmp != s) {
      for (auto &j : adj[tmp]) {
        if (s_dist[j.second] + j.first == s_dist[tmp]) {
          adj[j.second].emplace_back(0, tmp);
          tmp = j.second;
          break;
        }
      }
    }
    vector<ll> u_dist;
    dijkstra(u, u_dist);
    cout << u_dist[v] << '\n';
  }
}

int main() {
  // cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> s >> t >> u >> v;
  for (int i = 1; i <= m; i++) {
    int u, v; ll c;
    cin >> u >> v >> c;
    adj[u].emplace_back(c, v);
    adj[v].emplace_back(c, u);
  }
  if (s == u) sub1::Main();
  else if (n <= 300) sub3::Main();
  else sub2::Main();
}

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