제출 #847699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847699		nguyennh	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	344 ms	25496 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;

#define BIT(x, i) ((x) >> (i) & 1)
#define MASK(x) (1LL << x)
#define db(...) " [" << #__VA_ARGS__ ": " << (VA_ARGS) << "] "

#define N 100001

constexpr int64_t INF = numeric_limits<int64_t>::max() / 2;

int n, m;
int A, B, C, D;
int64_t dA[N], dB[N], dp[N][2][2];
vector<pair<int, int>> g[N];

struct Info { 
  int u;
  bool okay, used;
  int64_t c;
  Info() {};
  Info(int u, bool okay, bool used, int64_t c): u(u), okay(okay), used(used), c(c) {}; 
  friend bool operator < (const Info &a, const Info &b) {
    return a.c > b.c;
  }
};

template<class A, class B>
  inline bool mini(A &a, const B &b) {
    return a > b ? (a = b), true : false;
  }
  
void dijkstra(int s, int64_t d[]) {
  using T = pair<int64_t, int>;
  fill(d + 1, d + n + 1, INF);
  d[s] = 0;
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.emplace(0, s);
  while (pq.size()) {
    auto [c, u] = pq.top(); pq.pop();
    if (c > d[u]) continue;
    for (auto [v, w] : g[u]) if (mini(d[v], d[u] + w)) {
      pq.emplace(d[v], v);
    }
  }
}

int64_t f(int s, int t) {
  priority_queue<Info> pq;
  memset(dp, 0x3f, sizeof(dp));
  dp[s][0][0] = 0;
  pq.emplace(s, 0, 0, 0);
  auto inside = [&](int u, int v, int w) -> bool {
    return dA[u] + w + dB[v] == dA[B];
  };
  while (pq.size()) {
    auto [u, okay, used, c] = pq.top(); pq.pop();
    if (c != dp[u][okay][used]) continue;
    for (auto [v, w] : g[u]) {
      if (!used && inside(u, v, w) && mini(dp[v][1][used], c)) {
        pq.emplace(v, 1, used, c);
      }
      if (mini(dp[v][0][used || okay], c + w)) pq.emplace(v, 0, used || okay, c + w);
    }
  }
  int64_t res = INF;
  for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) mini(res, dp[t][i][j]);
  return res;
}

int main() {
//  freopen("tunnel.INP", "r", stdin);
//	freopen("tunnel.OUT", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  cin >> A >> B >> C >> D;
  for (int i = 1, u, v, c; i <= m; ++i) {
    cin >> u >> v >> c;
    g[u].emplace_back(v, c);
    g[v].emplace_back(u, c);
  }
  dijkstra(A, dA);
  dijkstra(B, dB);
  cout << min(f(C, D), f(D, C));
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'void dijkstra(int, int64_t*)':
commuter_pass.cpp:41:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     auto [c, u] = pq.top(); pq.pop();
      |          ^
commuter_pass.cpp:43:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for (auto [v, w] : g[u]) if (mini(d[v], d[u] + w)) {
      |               ^
commuter_pass.cpp: In function 'int64_t f(int, int)':
commuter_pass.cpp:58:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     auto [u, okay, used, c] = pq.top(); pq.pop();
      |          ^
commuter_pass.cpp:60:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for (auto [v, w] : g[u]) {
      |               ^

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