Submission #1106232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106232		cabbit	Robot (JOI21_ho_t4)	C++14	0 / 100	585 ms	74428 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
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(nullptr);
 
  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[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:39:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |   for (auto [dat, u] : mp) {
      |             ^
Main.cpp:41:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for (auto &[v, w] : g[u]) {
      |                ^
Main.cpp:50:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |     auto [c, u] = pq.top(); pq.pop();
      |          ^
Main.cpp:54:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for (auto [v, w] : g[u]) {
      |               ^

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