Submission #897165

#	Time	Username	Problem	Language	Result	Execution time	Memory
897165		LittleFlowers__	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	624 ms	32084 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define int long long

int32_t main() {
  if (fopen("input.txt", "r")) {
    freopen("input.txt", "r", stdin);
  }

  cin.tie(0)->sync_with_stdio(0);

  using ii = pair<int, int>;

  int n, m, S, T, U, V; cin >> n >> m >> S >> T >> U >> V;
  vector<vector<ii>> ad(n + 1);
  for (int i = 0; i < m; ++i) {
    int u, v, c; cin >> u >> v >> c;
    ad[u].push_back({v, c});
    ad[v].push_back({u, c});
  }

  vector<int> fs(n + 1), ft(n + 1), fu(n + 1), fv(n + 1);

  function dijkstra = [&](int u, vector<int> &f) {
    fill(f.begin(), f.end(), 1e14);
    priority_queue<ii, vector<ii>, greater<ii>> q;
    q.push({f[u] = 0, u});

    while (q.size()) {
      auto [w, u] = q.top(); q.pop();
      for (auto [v, c] : ad[u]) {
        if (f[v] > w + c) {
          f[v] = w + c;
          q.push({f[v], v});
        }
      }
    }
  };

  dijkstra(S, fs);
  dijkstra(T, ft);
  dijkstra(U, fu);
  dijkstra(V, fv);

  int answer = LLONG_MAX;
  for (int i = 0; i < 2; ++i) {
    vector<vector<int>> f(n + 1, vector<int>(2, 1e14));
    using iii = tuple<int, int, int>;
    priority_queue<iii, vector<iii>, greater<iii>> q;
    q.push(make_tuple(f[U][0] = 0, U, 0));

    while (q.size()) {
      auto [w, u, s] = q.top(); q.pop();

      answer = min(answer, w + fv[u]);
      for (auto [v, c] : ad[u]) {
        auto onpath = fs[u] + c + ft[v] == fs[T];

        if (f[v][s] > w + c) {
          f[v][s] = w + c;
          q.push(make_tuple(f[v][s], v, s));
        }

        if (onpath && f[v][1] > w) {
          f[v][1] = w;
          q.push(make_tuple(f[v][1], v, 1));
        }
      }
    }
    
    swap(U, V); swap(fu, fv);
  }

  cout << answer << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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