Submission #958476

#TimeUsernameProblemLanguageResultExecution timeMemory
958476BhavayGoyalOlympic Bus (JOI20_ho_t4)C++14
5 / 100
77 ms7688 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define vi vector<int> #define vii vector<vector<int>> #define pii pair<int, int> #define pb push_back #define f first #define s second #define endl "\n" const int linf = 1e15; // -------------------------------------------------- Main Code -------------------------------------------------- const int N = 201, M = 50001; int n, m; set<pii> g[N]; vii edges; map<pair<int, int>, bool> isShort; void dijkstra(int source) { priority_queue<pii, vector<pii>, greater<>> q; vi vis(n+1, 0), dis(n+1, linf), par(n+1); q.push({0, source}); dis[source] = 0; while (!q.empty()) { pii f = q.top(); q.pop(); int src = f.s; if (vis[src]) continue; vis[src] = true; for (auto child : g[src]) { int ch = child.f, wt = child.s; if (dis[ch] > dis[src] + wt) { par[ch] = src; dis[ch] = dis[src] + wt; q.push({dis[ch], ch}); } } } int x = (source==1?n:1); while (par[x]) { isShort[{par[x], x}] = true; x = par[x]; } } int get_dist(int s, int t) { vi D(n+1, linf); priority_queue<pii, vector<pii>, greater<pii>> pq; D[s] = 0; pq.emplace(0, s); while (pq.size()) { pii temp = pq.top(); int x = temp.f, u = temp.s; pq.pop(); if (D[u] == x) { for (pii child : g[u]) { int v = child.f, wt = child.s; if (D[v] > x + wt) { pq.emplace(D[v] = x + wt, v); } } } } return D[t]; } void sol() { cin >> n >> m; vii dist(n+1, vi(n+1, linf)); for (int i = 1; i <= n; i++) dist[i][i] = 0; for (int i = 1; i <= m; i++) { int a, b, c, d; cin >> a >> b >> c >> d; dist[a][b] = min(dist[a][b], c); g[a].insert({b, c}); edges.pb({a, b, c, d}); } dijkstra(1); dijkstra(n); for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } int ans = min(linf, dist[1][n] + dist[n][1]); for (auto i : edges) { int a = i[0], b = i[1], c = i[2], d = i[3]; if (isShort[{a, b}]) { int a = i[0], b = i[1], c = i[2], d = i[3]; g[a].erase({b, c}); g[b].insert({a, c}); ans = min(ans, get_dist(1, n) + get_dist(n, 1) + d); g[b].erase({a, c}); g[a].insert({b, c}); } else { int A = min(dist[1][n], dist[1][b] + c + dist[a][n]); int B = min(dist[n][1], dist[n][b] + c + dist[a][1]); if (A < linf && B < linf) { ans = min(ans, A + B + d); } } } cout << (ans==linf?-1:ans) << endl; } signed main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { sol(); } 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...