Submission #1167654

#TimeUsernameProblemLanguageResultExecution timeMemory
1167654kunzaZa183Olympic Bus (JOI20_ho_t4)C++20
11 / 100
73 ms5452 KiB
#include <bits/stdc++.h> using namespace std; #define int long long signed main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; vector<vector<int>> elist; elist.push_back({0, 0, 0, 0}); vector<vector<int>> floyd(n, vector<int>(n, INT_MAX)); for (int i = 0; i < n; i++) { floyd[i][i] = 0; } vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>()); for (int i = 0; i < m; i++) { int a, b, c, d; cin >> a >> b >> c >> d; a--, b--; elist.push_back({a, b, c, d}); floyd[a][b] = min(floyd[a][b], c); adj[a].emplace_back(b, c); } for (int times = 0; times < 6; times++) for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]); } } } auto dijkstra = [&](vector<int>& visited, int a, int b) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqpii; pqpii.emplace(a, b); while (!pqpii.empty()) { pair<int, int> cur = pqpii.top(); pqpii.pop(); if (visited[cur.second] != INT_MAX) continue; visited[cur.second] = cur.first; for (auto a : adj[cur.second]) pqpii.emplace(a.second + cur.first, a.first); } }; // for (int i = 0; i < n; i++) { // for (int j = 0; j < n; j++) { // cout << floyd[i][j] << " "; // } // cout << "\n"; // } int minans = INT_MAX; for (int i = 0; i <= m; i++) { vector<int> c1(floyd[0]), c2(floyd[n - 1]); int u = elist[i][1], v = elist[i][0], cst = elist[i][2]; c1[v] = min(c1[v], c1[u] + cst); c2[v] = min(c2[v], c2[u] + cst); for (int j = 0; j < n; j++) { c1[j] = min(c1[j], c1[v] + floyd[v][j]); c2[j] = min(c2[j], c2[v] + floyd[v][j]); } // cout << i << " " << c1[n - 1] << " " << c2[0] << " " << elist[i][3] << // "\n"; minans = min(minans, c1[n - 1] + c2[0] + elist[i][3]); } if (minans == INT_MAX) { cout << "-1\n"; } else cout << minans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...