Submission #19530828


Source Code Expand

Copy
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define debugArray(x, n)                                      \
  cerr << __LINE__ << ": " << #x << " = {";                   \
  for (long long hoge = 0; (hoge) < (long long)(n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];                   \
  cerr << "}" << '\n'
#define debugMatrix(x, h, w)                                         \
  cerr << __LINE__ << ": " << #x << " =\n";                          \
  for (long long hoge = 0; (hoge) < (long long)(h); ++(hoge)) {      \
    cerr << ((hoge ? " {" : "{{"));                                  \
    for (long long fuga = 0; (fuga) < (long long)(w); ++(fuga))      \
      cerr << ((fuga ? ", " : "")) << x[hoge][fuga];                 \
    cerr << "}" << (hoge + 1 == (long long)(h) ? "}" : ",") << '\n'; \
  }
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int N, M;
  cin >> N >> M;
  vector<pair<int, long long>> graph[N * 28];
  auto node = [](int n, int r) { return n * 28 + r % 28; };
  for (int i = 0; i < M; i++) {
    int f, t, c;
    cin >> f >> t >> c;
    if (f > t) swap(f, t);
    for (int r = 0; r < 28; r++)
      graph[node(f, r)].emplace_back(node(t, r + c), c);
    if (t != N - 1)
      for (int r = 0; r < 28; r++)
        graph[node(t, r)].emplace_back(node(f, r + c), c);
  }
  priority_queue<pair<long long, int>> pq;
  pq.emplace(0, 0);
  long long dist[N * 28];
  const long long INF = LLONG_MAX / 20;
  fill_n(dist, N * 28, INF);
  dist[0] = 0;
  while (!pq.empty()) {
    auto [d, v] = pq.top();
    pq.pop();
    d = -d;
    if (dist[v] < d) continue;
    for (auto [u, c] : graph[v])
      if (dist[u] > dist[v] + c) {
        dist[u] = dist[v] + c;
        pq.emplace(-dist[u], u);
      }
  }
  long long ans = INF;
  for (int r = 0; r < 28; r++)
    if (r % 4 == 0 || r % 7 == 0) ans = min(ans, dist[node(N - 1, r)]);
  cout << ans << '\n';
  return 0;
}

Submission Info

Submission Time
Task E - 会場への道
User hashiryo
Language C++ (GCC 9.2.1)
Score 100
Code Size 2387 Byte
Status AC
Exec Time 43 ms
Memory 19904 KB

Judge Result

Set Name sub1 sub2
Score / Max Score 30 / 30 70 / 70
Status
AC × 15
AC × 26
Set Name Test Cases
sub1 sub1/input_0.txt, sub1/input_1.txt, sub1/input_2.txt, sub1/input_20.txt, sub1/input_21.txt, sub1/input_22.txt, sub1/input_23.txt, sub1/input_24.txt, sub1/input_3.txt, sub1/input_4.txt, sub1/input_5.txt, sub1/input_6.txt, sub1/input_7.txt, sub1/input_8.txt, sub1/input_9.txt
sub2 sub2/input_0.txt, sub2/input_1.txt, sub2/input_10.txt, sub2/input_11.txt, sub2/input_12.txt, sub2/input_13.txt, sub2/input_14.txt, sub2/input_15.txt, sub2/input_16.txt, sub2/input_17.txt, sub2/input_18.txt, sub2/input_19.txt, sub2/input_2.txt, sub2/input_20.txt, sub2/input_21.txt, sub2/input_22.txt, sub2/input_23.txt, sub2/input_24.txt, sub2/input_25.txt, sub2/input_3.txt, sub2/input_4.txt, sub2/input_5.txt, sub2/input_6.txt, sub2/input_7.txt, sub2/input_8.txt, sub2/input_9.txt
Case Name Status Exec Time Memory
sub1/input_0.txt AC 8 ms 3476 KB
sub1/input_1.txt AC 2 ms 3468 KB
sub1/input_2.txt AC 2 ms 3608 KB
sub1/input_20.txt AC 10 ms 5288 KB
sub1/input_21.txt AC 6 ms 4540 KB
sub1/input_22.txt AC 11 ms 4476 KB
sub1/input_23.txt AC 4 ms 3820 KB
sub1/input_24.txt AC 6 ms 4684 KB
sub1/input_3.txt AC 9 ms 3600 KB
sub1/input_4.txt AC 2 ms 3544 KB
sub1/input_5.txt AC 2 ms 3624 KB
sub1/input_6.txt AC 2 ms 3624 KB
sub1/input_7.txt AC 2 ms 3476 KB
sub1/input_8.txt AC 2 ms 3552 KB
sub1/input_9.txt AC 4 ms 3584 KB
sub2/input_0.txt AC 2 ms 3544 KB
sub2/input_1.txt AC 2 ms 3464 KB
sub2/input_10.txt AC 11 ms 5732 KB
sub2/input_11.txt AC 38 ms 17140 KB
sub2/input_12.txt AC 37 ms 17216 KB
sub2/input_13.txt AC 11 ms 5672 KB
sub2/input_14.txt AC 35 ms 17056 KB
sub2/input_15.txt AC 35 ms 17116 KB
sub2/input_16.txt AC 43 ms 18424 KB
sub2/input_17.txt AC 39 ms 17060 KB
sub2/input_18.txt AC 39 ms 17124 KB
sub2/input_19.txt AC 42 ms 19904 KB
sub2/input_2.txt AC 5 ms 3616 KB
sub2/input_20.txt AC 11 ms 5228 KB
sub2/input_21.txt AC 11 ms 4488 KB
sub2/input_22.txt AC 6 ms 4496 KB
sub2/input_23.txt AC 3 ms 3736 KB
sub2/input_24.txt AC 7 ms 4600 KB
sub2/input_25.txt AC 10 ms 5784 KB
sub2/input_3.txt AC 2 ms 3548 KB
sub2/input_4.txt AC 2 ms 3480 KB
sub2/input_5.txt AC 2 ms 3600 KB
sub2/input_6.txt AC 2 ms 3428 KB
sub2/input_7.txt AC 1 ms 3480 KB
sub2/input_8.txt AC 2 ms 3548 KB
sub2/input_9.txt AC 2 ms 3652 KB