Submission #8043629


Source Code Expand

Copy
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <stack>
#include <queue>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

template <class T> inline bool chmin(T &a, const T &b) {
  return (a > b) ? a = b, true : false;
}

template <class T> inline bool chmax(T &a, const T &b) {
  return (a < b) ? a = b, true : false;
}

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

// void bfs(const Graph & g, const int s) {

// }

using Graph = std::vector<std::vector<std::pair<int, int>>>;

int main() {
  int n, m, l;
  std::cin >> n >> m >> l;
  std::vector<int> a(m);
  std::vector<int> b(m);
  std::vector<int> c(m);
  for (int i = 0; i < m; ++i) {
    std::cin >> a[i] >> b[i] >> c[i];
    a[i] -= 1;
    b[i] -= 1;
  }

  int q;
  std::cin >> q;
  std::vector<int> s(q);
  std::vector<int> t(q);
  for (int k = 0; k < q; ++k) {
    std::cin >> s[k] >> t[k];
    s[k] -= 1;
    t[k] -= 1;
  }

  Graph g_org(n);
  for (int i = 0; i < m; ++i) {
    if (c[i] > l)
      continue;
    g_org[a[i]].push_back(std::make_pair(b[i], c[i]));
    g_org[b[i]].push_back(std::make_pair(a[i], c[i]));
  }

  // 全頂点対間最短路を求める
  std::vector<std::vector<long long>> dp(n, std::vector<long long>(n, LINF));
  for (int i = 0; i < n; ++i)
    dp[i][i] = 0;
  for (int i = 0; i < m; ++i) {
    dp[a[i]][b[i]] = c[i];
    dp[b[i]][a[i]] = c[i];
  }
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[k][j]);
      }
    }
  }

  Graph g_new(n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == j)
        continue;
      if (dp[i][j] > l)
        continue;
      g_new[i].push_back(std::make_pair(j, dp[i][j]));
    }
  }

  // for (int v = 0; v < n; ++v) {
  //   std::cout << v << ": ";
  //   for (auto wc : g_new[v]) {
  //     std::cout << wc.first << "," << wc.second << " ";
  //   }
  //   std::cout << std::endl;
  // }

  std::vector<std::vector<long long>> dp_new(n, std::vector<long long>(n, LINF));
  for (int i = 0; i < n; ++i)
    dp_new[i][i] = 0;
  // for (int i = 0; i < m; ++i) {
  //   dp[a[i]][b[i]] = c[i];
  //   dp[b[i]][a[i]] = c[i];
  // }
  for (int v = 0; v < n; ++v) {
    for (auto wc: g_new[v])
      dp_new[v][wc.first] = 1;
  }
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        dp_new[i][j] = std::min(dp_new[i][j], dp_new[i][k] + dp_new[k][j]);
      }
    }
  }

  for (int k = 0; k < q; ++k) {
    if (dp_new[s[k]][t[k]] == LINF)
      std::cout << -1 << std::endl;
    else
      std::cout << dp_new[s[k]][t[k]] - 1 << std::endl;
  }

  return 0;
}

Submission Info

Submission Time
Task E - Travel by Car
User KuroUron
Language C++14 (GCC 5.4.1)
Score 500
Code Size 3604 Byte
Status AC
Exec Time 272 ms
Memory 5504 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 50
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 02-random-08, 02-random-09, 02-random-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 256 KB
00-sample-01 AC 1 ms 256 KB
00-sample-02 AC 1 ms 256 KB
01-handmade-03 AC 234 ms 2688 KB
01-handmade-04 AC 272 ms 5504 KB
01-handmade-05 AC 269 ms 4352 KB
01-handmade-06 AC 233 ms 2688 KB
01-handmade-07 AC 236 ms 2688 KB
02-random-08 AC 4 ms 384 KB
02-random-09 AC 17 ms 512 KB
02-random-10 AC 234 ms 2688 KB
02-random-11 AC 11 ms 384 KB
02-random-12 AC 26 ms 640 KB
02-random-13 AC 32 ms 768 KB
02-random-14 AC 189 ms 3328 KB
02-random-15 AC 234 ms 2688 KB
02-random-16 AC 87 ms 1280 KB
02-random-17 AC 140 ms 1792 KB
02-random-18 AC 12 ms 512 KB
02-random-19 AC 2 ms 256 KB
02-random-20 AC 233 ms 2688 KB
02-random-21 AC 47 ms 768 KB
02-random-22 AC 1 ms 256 KB
02-random-23 AC 76 ms 1664 KB
02-random-24 AC 218 ms 4224 KB
02-random-25 AC 234 ms 2688 KB
02-random-26 AC 3 ms 256 KB
02-random-27 AC 107 ms 1408 KB
02-random-28 AC 119 ms 2432 KB
02-random-29 AC 103 ms 2176 KB
02-random-30 AC 233 ms 2560 KB
02-random-31 AC 12 ms 384 KB
02-random-32 AC 78 ms 1152 KB
02-random-33 AC 97 ms 1792 KB
02-random-34 AC 77 ms 1792 KB
02-random-35 AC 233 ms 2688 KB
02-random-36 AC 68 ms 1024 KB
02-random-37 AC 89 ms 1280 KB
02-random-38 AC 1 ms 256 KB
02-random-39 AC 5 ms 384 KB
02-random-40 AC 229 ms 2688 KB
02-random-41 AC 227 ms 2560 KB
02-random-42 AC 39 ms 768 KB
02-random-43 AC 207 ms 4096 KB
02-random-44 AC 2 ms 256 KB
02-random-45 AC 235 ms 2688 KB
02-random-46 AC 16 ms 512 KB
02-random-47 AC 172 ms 2048 KB
02-random-48 AC 1 ms 256 KB
02-random-49 AC 24 ms 768 KB