제출 #958509

#제출 시각아이디문제언어결과실행 시간메모리
958509BhavayGoyalOlympic Bus (JOI20_ho_t4)C++14
0 / 100
43 ms5752 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 inf = 1e15; // -------------------------------------------------- Main Code -------------------------------------------------- const int N = 201, M = 50001; int n, m, aa[M], bb[M], cc[M], dd[M], dis[N], vis[N], dist[N][N], isShort[M]; set<pii> g[N]; void dijkstra(int source) { priority_queue<pii, vector<pii>, greater<>> q; vi vis(n+1, 0), dis(n+1, inf), par(n+1), idx(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 = cc[child.s]; if (dis[ch] > dis[src] + wt) { par[ch] = src; idx[ch] = child.s; dis[ch] = dis[src] + wt; q.push({dis[ch], ch}); } } } int x = (source==1?n:1); while (par[x]) { isShort[idx[x]] = true; x = par[x]; } } int get_dist(int s, int t) { vi D(n+1, inf); 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; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i != j) dist[i][j] = inf; for (int i = 1; i <= m; i++) { cin >> aa[i] >> bb[i] >> cc[i] >> dd[i]; dist[aa[i]][bb[i]] = min(dist[aa[i]][bb[i]], cc[i]); g[aa[i]].insert({bb[i], i}); } 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(inf, dist[1][n] + dist[n][1]); for (int i = 1; i <= m; i++) { int a = aa[i], b = bb[i], c = cc[i], d = dd[i]; if (isShort[i]) { g[a].erase(g[a].find({b, i})); g[b].insert({a, i}); ans = min(ans, get_dist(1, n) + get_dist(n, 1) + d); g[b].erase(g[b].find({a, i})); g[a].insert({b, i}); } 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]); ans = min(ans, A + B + d); } } cout << (ans==inf?-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...