Submission #605434

#	Time	Username	Problem	Language	Result	Execution time	Memory
605434		jjiangly	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	474 ms	40264 KiB

commuter_pass

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

#define all(x) x.begin(), x.end()
#define siz(x) int(x.size())
#define ll long long
#define ar array
#define vt vector
#define inf int(1e9)
#define lnf (long long) 1e15

const int nxm = int(1e5) + 7;
int n, m, S, T, U, V;

namespace sub1 {
  vt<vt<ar<int, 2>>> e(nxm);
  vt<vt<ll>> d(3, vt<ll> (nxm, lnf));
  void exe() {
    for (int i = 0; i < m; ++i) {
      int a, b, c;
      cin >> a >> b >> c;
      --a, --b;
      e[a].push_back({c, b});
      e[b].push_back({c, a});
    }
    function<void(int, int)> dijkstra = [&](int root, int id) {
      priority_queue<ar<ll, 2>, vt<ar<ll, 2>>, greater<ar<ll, 2>>> que;
      que.push({0, root});
      d[id][root] = 0;
      while (que.size()) {
        ll du = que.top()[0];
        int u = que.top()[1];
        que.pop();
        if (du != d[id][u]) {
          continue;
        }
        for (int i = 0; i < siz(e[u]); ++i) {
          ll c = e[u][i][0];
          int v = e[u][i][1];
          if (d[id][v] > du + c) {
            d[id][v] = du + c;
            que.push({d[id][v], v});
          }
        }
      }
    };
    dijkstra(S, 0);
    dijkstra(T, 1);
    dijkstra(V, 2);
    ll ans = d[0][V];
    for (int i = 0; i < n; ++i) {
      if (d[0][i] + d[1][i] == d[0][T]) {
        ans = min(ans, d[2][i]);
      }
    }
    cout << ans << "\n";
  }
};

namespace sub2 {
  vt<vt<ar<int, 2>>> e(nxm);
  vt<vt<ll>> d(4, vt<ll> (nxm, lnf));
  void exe() {
    for (int i = 0; i < m; ++i) {
      int a, b, c;
      cin >> a >> b >> c;
      --a, --b;
      e[a].push_back({c, b});
      e[b].push_back({c, a});
    }
    function<void(int, int)> dijkstra = [&](int root, int id) {
      priority_queue<ar<ll, 2>, vt<ar<ll, 2>>, greater<ar<ll, 2>>> que;
      que.push({0, root});
      d[id][root] = 0;
      while (que.size()) {
        ll du = que.top()[0];
        int u = que.top()[1];
        que.pop();
        if (d[id][u] != du) {
          continue;
        }
        for (int i = 0; i < siz(e[u]); ++i) {
          ll c = e[u][i][0];
          int v = e[u][i][1];
          if (d[id][v] > du + c) {
            d[id][v] = du + c;
            que.push({d[id][v], v});
          }
        }
      }
    };
    dijkstra(S, 0);
    dijkstra(T, 1);
    dijkstra(U, 2);
    dijkstra(V, 3);
    vt<int> path;
    for (int i = 0; i < n; ++i) {
      if (d[0][i] + d[1][i] == d[0][T]) {
        path.push_back(i);
      }
    }
    ll ans = d[2][V];
    ll r = lnf, r2 = lnf;
    for (int i : path) {
      r = min(r, d[2][i]);
      r2 = min(r2, d[3][i]);
    }
    cout << min(ans, r + r2) << "\n";
  }
};

namespace sub3 {
  ll e[305][305];
  void exe() {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        e[i][j] = lnf;
      }
    }
    for (int i = 0; i < n; ++i) {
      e[i][i] = 0;
    }
    for (int i = 0; i < m; ++i) {
      int a, b;
      cin >> a >> b;
      --a, --b;
      cin >> e[a][b];
      e[b][a] = e[a][b];
    }
    for (int k = 0; k < n; ++k) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          if (e[i][k] != lnf && e[k][j] != lnf) {
            e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
          }
        }
      }
    }
    ll ans = e[U][V];
    //cout << e[4][0] + e[0][1] + e[1][6] << " " << e[4][6] << " " << e[5][1] << " " << e[0][7] << "\n";
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (e[S][i] + e[i][j] + e[j][T] == e[S][T]) {
          ans = min(ans, e[U][i] + e[j][V]);
          ans = min(ans, e[U][j] + e[i][V]);
        }
      }
    }
    cout << ans << "\n";
  }
};

namespace sub4 {
  vt<vt<ar<int, 3>>> e(nxm);
  vt<vt<ll>> d(4, vt<ll> (nxm, lnf));
  void exe() {
    for (int i = 0; i < m; ++i) {
      int a, b, c;
      cin >> a >> b >> c;
      --a, --b;
      e[a].push_back({c, b});
      e[b].push_back({c, a});
    }
    function<void(int, int)> dijkstra = [&](int root, int id) {
      priority_queue<ar<ll, 2>, vt<ar<ll, 2>>, greater<ar<ll, 2>>> que;
      que.push({0, root});
      d[id][root] = 0;
      while (que.size()) {
        ll du = que.top()[0];
        int u = que.top()[1];
        que.pop();
        if (du != d[id][u]) {
          continue;
        }
        for (int i = 0; i < siz(e[u]); ++i) {
          ll c = e[u][i][0];
          int v = e[u][i][1];
          if (d[id][v] > du + c) {
            d[id][v] = du + c;
            que.push({d[id][v], v});
          }
        }
      }
    };
    dijkstra(S, 0);
    dijkstra(T, 1);
    dijkstra(U, 2);
    dijkstra(V, 3);
    vt<vt<int>> p(n);
    function<void(int)> work = [&](int root) {
      priority_queue<ar<ll, 2>, vt<ar<ll, 2>>, greater<ar<ll, 2>>> que;
      que.push({0, root});
      vt<ll> d2(n, lnf);
      d2[root] = 0;
      while (que.size()) {
        ll du = que.top()[0];
        int u = que.top()[1];
        que.pop();
        if (du != d2[u]) {
          continue;
        }
        for (int i = 0; i < siz(e[u]); ++i) {
          ll c = e[u][i][0];
          int v = e[u][i][1];
          if (d2[v] > du + c) {
            d2[v] = du + c;
            que.push({d2[v], v});
          }
          if (du + c == d[0][v]) {
            p[v].push_back(u);
          }
        }
      }
    };
    work(S);
    vt<vt<int>> child(n);
    queue<int> que;
    que.push(T);
    vt<bool> vis(n, false);
    while (que.size()) {
      int u = que.front();
      que.pop();
      if (!vis[u]) {
        vis[u] = true;
        for (int v : p[u]) {
          child[v].push_back(u);
          que.push(v);
        }
      }
    }
    vt<ll> dp(n, -1);
    vt<ll> dp2(n, -1);
    function<ll(int)> dpnext = [&](int u) {
      if (dp[u] != -1) {
        return dp[u];
      }
      ll res = d[3][u];
      for (int v : child[u]) {
        res = min(res, dpnext(v));
      }
      return dp[u] = res;
    };
    function<ll(int)> dpforward = [&](int u) {
      if (dp2[u] != -1) {
        return dp2[u];
      }
      ll res = d[3][u];
      for (int v : p[u]) {
        res = min(res, dpforward(v));
      }
      return dp2[u] = res;
    };
    ll ans = d[3][U];
    for (int i = 0; i < n; ++i) {
      if (vis[i]) {
        ans = min(ans, d[2][i] + min(dpnext(i), dpforward(i)));
      }
    }
    cout << ans << "\n";
  }
};

int subtask() {
  if (S == U) {
    return 1;
  } else if (n <= 300) {
    return 3;
  }
  return 4;
}

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

  cin >> n >> m >> S >> T >> U >> V;
  --S, --T, --U, --V;
  if (subtask() == 1) {
    sub1::exe();
  } else if (subtask() == 2) {
    sub2::exe();
  } else if (subtask() == 3) {
    sub3::exe();
  } else {
    sub4::exe();
  }

  return 0;
}

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