Submission #605314

#	Time	Username	Problem	Language	Result	Execution time	Memory
605314		jjiangly	Commuter Pass (JOI18_commuter_pass)	C++14	40 / 100	2064 ms	24412 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, 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 (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];
    for (int i : path) {
      for (int j : path) {
        if (i != j) {
          ans = min(ans, d[2][i] + d[3][j]);
        }
      }
    }
    cout << ans << "\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";
  }
};

int subtask() {
  if (s == u) {
    return 1;
  } else if (n <= 300) {
    return 3;
  }
  return 2;
}

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();
  }

  return 0;
}

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