Submission #897140

#	Time	Username	Problem	Language	Result	Execution time	Memory
897140		duckindog	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	396 ms	33996 KiB

commuter_pass

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

using namespace std;

#define int long long

using pii = pair<int, int>;
using T = tuple<int, int, int>;
const int N = 1e5 + 10;
int n, m;
int s, t, u, v;
vector<pair<int, int>> ad[N];
int f[N], sv[N];
void sktra(int x) {
  memset(f, 40, 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;
      if (f[v] > dis + w)
        q.emplace(f[v] = dis + w, v);
    }
  }
}
bool dd[N];
int d[N][10];
void dijsktra(int x) {
  memset(d, 40, sizeof d);
  priority_queue<T, vector<T>, greater<T>> q;
  q.emplace(d[x][dd[x]] = 0, x, dd[x]);
  while (q.size()) {
    int dis, u, st; tie(dis, u, st) = q.top(); q.pop();
    if (dis != d[u][st]) continue;
    for (auto duck : ad[u]) {
      int v, w; tie(v, w) = duck;

      int nst = 2;
      if (!st && dd[v]) nst = 1;
      else if (st == 2) nst = 2;
      else if (st == 1 && dd[v]) nst = (sv[u] + f[v] + w == sv[t] ? 1 : 2);
      int val = dis + w * (nst == 1 && st == 1 ? 0 : 1);
      if (d[v][nst] > val)
        q.emplace(d[v][nst] = val, v, nst);
      int se = !st;
      if (se && d[v][0] > dis + w)
        q.emplace(d[v][0] = dis + w, v, 0);
    }
  }
}

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;

  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);
  for (int i = 1; i <= n; ++i) sv[i] = f[i];
  sktra(t);
  for (int i = 1; i <= n; ++i) dd[i] = (sv[i] + f[i] == f[s]);
  int answer = 1e14;
  dijsktra(v);
  answer = min({answer, d[u][0], d[u][1], d[u][2]});
  dijsktra(u);
  answer = min({answer, d[v][0], d[v][1], d[v][2]});
  cout << answer;

}

Compilation message (stderr)

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

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