Submission #896919

#	Time	Username	Problem	Language	Result	Execution time	Memory
896919		duckindog	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2013 ms	51100 KiB

commuter_pass

// from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

#define int long long

using pii = pair<int, int>;
const int N = 1e5 + 10,
          M = 310;
int n, m;
int s, t, u, v;
vector<pair<int, int>> ad[N];
int f[N], trace[N];
map<int, int> d[N];
void sktra(int x) {
  memset(f, 63, sizeof f);
  priority_queue<pii, vector<pii>, greater<pii>> q;
  q.emplace(f[x] = 0, x);
  while (q.size()) {
    int dis, u; tie(dis, u) = q.top(); q.pop();
    if (dis != f[u]) continue;
    for (auto duck : ad[u]) {
      int v, w; tie(v, w) = duck;
      int val = dis + w * (1 - d[u][v]);
      if (f[v] > val) {
        q.emplace(f[v] = val, v);
        trace[v] = u;
      }
    }
  }
}
int dp[M][M];
int siesthree = 2e14;
void dfs(int a, int pre, int dis) {
  if (dis != dp[s][a]) return;
  d[a][pre] = d[pre][a] = 1;
  if (a == t) {
    sktra(u);
    siesthree = min(siesthree, f[v]);
  }
  for (auto duck : ad[a]) {
    int b, w; tie(b, w) = duck;
    if (b == pre) continue;
    dfs(b, a, dis + w);
  }
  d[a][pre] = d[pre][a] = 0;
}
void sub3() {
  memset(dp, 63, sizeof dp);

  for (int i = 1; i <= n; ++i) dp[i][i] = 0;
  for (int i = 1; i <= m; ++i) {
    int a, b, c; cin >> a >> b >> c;
    ad[a].push_back({b, c});
    ad[b].push_back({a, c});
    dp[a][b] = dp[b][a] = c;
  }

  for (int c = 1; c <= n; ++c)
    for (int a = 1; a <= n; ++a)
      for (int b = 1; b <= n; ++b)
        dp[a][b] = min(dp[a][b], dp[a][c] + dp[c][b]);
  dfs(s, 0, 0);
  cout << siesthree;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> n >> m;
  cin >> s >> t >> u >> v;

  if (n <= 300) {
    sub3();
    return 0;
  }

  for (int i = 1; i <= m; ++i) {
    int a, b, c; cin >> a >> b >> c;
    ad[a].push_back({b, c});
    ad[b].push_back({a, c});
  }
  sktra(s);
  int x = t;
  while (trace[x]) {
    d[x][trace[x]] = d[trace[x]][x] = 1;
    x = trace[x];
  }
  sktra(u);
  cout << f[v];
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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