Contest Duration: - (local time) (100 minutes) Back to Home

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 2019-10-19 22:19:31+0900 E - Travel by Car KuroUron C++14 (GCC 5.4.1) 500 3604 Byte AC 272 ms 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