Submission #532355

#TimeUsernameProblemLanguageResultExecution timeMemory
532355Alex_tz307Autobus (COCI22_autobus)C++17
70 / 70
167 ms6324 KiB
#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int64_t INFL = 1e18L; void minSelf(int &x, int y) { if (y < x) { x = y; } } void testCase() { int n, m; cin >> n >> m; vector<vector<int>> wt(n + 1, vector<int>(n + 1, INF)); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; minSelf(wt[u][v], w); } vector<vector<pair<int, int>>> g(n + 1); for (int u = 1; u <= n; ++u) { for (int v = 1; v <= n; ++v) { if (u != v && wt[u][v] != INF) { g[u].emplace_back(v, wt[u][v]); } } } int k, q; cin >> k >> q; minSelf(k, n); vector<vector<int64_t>> best(n + 1, vector<int64_t>(n + 1, INFL)); for (int s = 1; s <= n; ++s) { vector<vector<int64_t>> dp(n + 1, vector<int64_t>(k + 1, INFL)); /// costul minim sa ajung de la s la nod cu lungime len vector<vector<bool>> inQ(n + 1, vector<bool>(k + 1)); dp[s][0] = 0; queue<pair<int, int>> q; q.emplace(s, 0); inQ[s][0] = true; while (!q.empty()) { int u, len; tie(u, len) = q.front(); q.pop(); inQ[u][len] = false; for (auto it : g[u]) { int v, w; tie(v, w) = it; if (dp[v][len + 1] > dp[u][len] + w) { dp[v][len + 1] = dp[u][len] + w; if (len + 1 < k && !inQ[v][len + 1]) { q.emplace(v, len + 1); inQ[v][len + 1] = true; } } } } for (int t = 1; t <= n; ++t) { best[s][t] = *min_element(dp[t].begin(), dp[t].end()); } } for (int i = 0; i < q; ++i) { int s, t; cin >> s >> t; if (best[s][t] == INFL) { cout << "-1\n"; } else { cout << best[s][t] << '\n'; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tests = 1; for (int tc = 0; tc < tests; ++tc) { testCase(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...