Submission #1036067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036067		ToTenLinh	Robot (JOI21_ho_t4)	C++14	100 / 100	708 ms	83152 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, MAX = 5e5 + 5;
const long long inf = 1e18;
int n, m;
long long d[MAX], sum[MAX];
map<array<int, 2>, long long> mp;
vector<pair<int, long long>> g[MAX];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //freopen("robot1.inp", "r", stdin);
  //freopen("robot1.out", "w", stdout);
  cin >> n >> m;
  int tot = n;
  auto add = [&](int u, int c) {
    if (!mp.count({u, c})) {
      mp[{u, c}] = ++tot;
    }
    return mp[{u, c}];
  };
  for (int i = 1; i <= m; ++i) {
    int u, v, c, w; cin >> u >> v >> c >> w;
    for (int it = 0; it < 2; ++it) {
      swap(u, v);
      sum[add(u, c)] += w;
      g[u].push_back({v, w});
      g[u].push_back({add(v, c), 0});
      g[add(u, c)].push_back({v, -w});
    }
  }
  for (auto [dat, u] : mp) {
    g[dat[0]].push_back({u, 0});
    for (auto &[v, w] : g[u]) {
      w += sum[u];
    }
  }
  fill(d + 1, d + tot + 1, inf);
  using T = pair<long long, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.push({d[1] = 0, 1});
  while (pq.size()) {
    auto [c, u] = pq.top(); pq.pop();
    if (c != d[u]) {
      continue;
    }
    for (auto [v, w] : g[u]) {
      if (d[v] > d[u] + w) {
        pq.push({d[v] = d[u] + w, v});
      }
    }
  }
  cout << (d[n] == inf ? -1 : d[n]);
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:33:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |   for (auto [dat, u] : mp) {
      |             ^
Main.cpp:35:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for (auto &[v, w] : g[u]) {
      |                ^
Main.cpp:44:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     auto [c, u] = pq.top(); pq.pop();
      |          ^
Main.cpp:48:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for (auto [v, w] : g[u]) {
      |               ^

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42