Submission #757565

#TimeUsernameProblemLanguageResultExecution timeMemory
757565Desh03Olympic Bus (JOI20_ho_t4)C++17
5 / 100
1084 ms4504 KiB
#include <bits/stdc++.h> using namespace std; const long long INF = 1e18; vector<multiset<pair<int, int>>> g; void djikstra(int src, vector<long long> &sp) { priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; pq.push({sp[src] = 0, src}); while (pq.size()) { int u = pq.top().second; pq.pop(); for (auto [v, w] : g[u]) { if (sp[u] + w < sp[v]) sp[v] = sp[u] + w, pq.push({sp[v], v}); } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; g.resize(n); vector<long long> sp1, sp2; vector<tuple<int, int, int, int>> edges; for (int i = 0; i < m; i++) { int u, v, c, d; cin >> u >> v >> c >> d; --u, --v; g[u].insert({v, c}); edges.push_back({u, v, c, d}); } sp1 = sp2 = vector<long long> (n, INF); djikstra(0, sp1), djikstra(n - 1, sp2); long long ans = min(INF, sp1[n - 1] + sp2[0]); for (auto [u, v, c, d] : edges) { g[u].erase(g[u].find({v, c})); g[v].insert({u, c}); sp1 = sp2 = vector<long long> (n, INF); djikstra(0, sp1), djikstra(n - 1, sp2); ans = min(ans, sp1[n - 1] + sp2[0] + d); g[v].erase(g[v].find({u, c})); g[u].insert({v, c}); } cout << (ans == INF ? -1 : ans) << '\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...