제출 #684947

#제출 시각아이디문제언어결과실행 시간메모리
684947etheningOlympic Bus (JOI20_ho_t4)C++17
0 / 100
792 ms4052 KiB
#include "bits/stdc++.h" #include <functional> #include <queue> #include <vector> using namespace std; using ll = long long; using pii = pair<int, int>; const int MAXN = 200; const int MAXM = 50000; const ll INF = 1000'000'000'000'000ll; int n, m; struct edge { int fr, to; ll wcost; ll scost; bool crit; }; edge E[MAXM + 5]; vector<int> v[MAXN + 5], v2[MAXN + 5]; vector<vector<int>> adj; vector<vector<int>> adj2; int get_edge(int a, int b, int swapEg) { int ret = -1; if (swapEg != -1 && E[swapEg].fr == b && E[swapEg].to == a) { ret = swapEg; } if (adj[a][b] != -1 && adj[a][b] != swapEg) { if (ret == -1 || E[adj[a][b]].wcost < E[ret].wcost) { ret = adj[a][b]; } } if (adj2[a][b] != -1 && adj2[a][b] != swapEg) { if (ret == -1 || E[adj2[a][b]].wcost < E[ret].wcost) { ret = adj2[a][b]; } } return ret; } void dijk(int source, vector<ll>& dist) { dist.assign(n + 5, INF); vector<bool> vis(n + 5, false); typedef pair<ll, int> pli; priority_queue<pli, vector<pli>, greater<pli>> Q; dist[source] = 0; vector<int> arrEdge(n + 5, 0); for (int k = 1; k <= n; k++) { int a = -1; ll min = INF; for (int i = 1; i <= n; i++) { if (!vis[i] && dist[i] < min) { a = i; min = dist[i]; } } if (a == -1) break; vis[a] = true; for (int b = 1; b <= n; b++) { int eg = get_edge(a, b, -1); if (eg == -1) continue; if (!vis[b] && dist[a] + E[eg].wcost < dist[b]) { dist[b] = dist[a] + E[eg].wcost; arrEdge[b] = eg; } } } for (int i = 1; i <= n; i++) { if (arrEdge[i] != 0) { E[arrEdge[i]].crit = true; } } } void dijk2(int dest, vector<ll>& dist) { dist.assign(n + 5, INF); vector<bool> vis(n + 5, false); typedef pair<ll, int> pli; priority_queue<pli, vector<pli>, greater<pli>> Q; dist[dest] = 0; vector<int> arrEdge(n + 5, 0); for (int k = 1; k <= n; k++) { int a = -1; ll min = INF; for (int i = 1; i <= n; i++) { if (!vis[i] && dist[i] < min) { a = i; min = dist[i]; } } if (a == -1) break; vis[a] = true; for (int b = 1; b <= n; b++) { int eg = get_edge(b, a, -1); if (eg == -1) continue; if (!vis[b] && dist[a] + E[eg].wcost < dist[b]) { dist[b] = dist[a] + E[eg].wcost; arrEdge[b] = eg; } } } for (int i = 1; i <= n; i++) { if (arrEdge[i] != 0) { E[arrEdge[i]].crit = true; } } } void dijk3(int source, vector<ll>& dist, int swapEg) { dist.assign(n + 5, INF); vector<bool> vis(n + 5, false); typedef pair<ll, int> pli; priority_queue<pli, vector<pli>, greater<pli>> Q; dist[source] = 0; for (int k = 1; k <= n; k++) { int a = -1; ll min = INF; for (int i = 1; i <= n; i++) { if (!vis[i] && dist[i] < min) { a = i; min = dist[i]; } } if (a == -1) break; vis[a] = true; for (int b = 1; b <= n; b++) { int eg = get_edge(a, b, swapEg); if (eg == -1) continue; if (!vis[b] && dist[a] + E[eg].wcost < dist[b]) { dist[b] = dist[a] + E[eg].wcost; } } } } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> E[i].fr >> E[i].to >> E[i].wcost >> E[i].scost; E[i].crit = false; v[E[i].fr].push_back(i); v2[E[i].to].push_back(i); } adj.assign(n + 5, vector<int>(n + 5, -1)); adj2.assign(n + 5, vector<int>(n + 5, -1)); for (int i = 1; i <= m; i++) { if (adj[E[i].fr][E[i].to] == -1) { adj[E[i].fr][E[i].to] = i; continue; } if (adj2[E[i].fr][E[i].to] == -1) { adj2[E[i].fr][E[i].to] = i; if (E[adj2[E[i].fr][E[i].to]].wcost < E[adj[E[i].fr][E[i].to]].wcost) { swap(adj[E[i].fr][E[i].to], adj2[E[i].fr][E[i].to]); } continue; } if (E[i].wcost < E[adj2[E[i].fr][E[i].to]].wcost) { adj2[E[i].fr][E[i].to] = i; if (E[adj2[E[i].fr][E[i].to]].wcost < E[adj[E[i].fr][E[i].to]].wcost) { swap(adj[E[i].fr][E[i].to], adj2[E[i].fr][E[i].to]); } } } vector<ll> distfr1, distton, distfrn, distto1; dijk(1, distfr1); dijk(n, distfrn); dijk2(1, distto1); dijk2(n, distton); // cout << "!!!" << endl; // for (int i = 1; i <= n; i++) { // cout << i << " " << distfr1[i] << endl; // } // cout << "!!!" << endl; // for (int i = 1; i <= n; i++) { // cout << i << " " << distfrn[i] << endl; // } // cout << "!!!" << endl; // for (int i = 1; i <= n; i++) { // cout << i << " " << distto1[i] << endl; // } // cout << "!!!" << endl; // for (int i = 1; i <= n; i++) { // cout << i << " " << distton[i] << endl; // } ll ans = INF; ans = min(ans, distfr1[n] + distfrn[1]); for (int i = 1; i <= m; i++) { if (E[i].crit) continue; ll tmp = min(distfr1[n], distfr1[E[i].to] + E[i].scost + E[i].wcost + distton[E[i].fr]); ll tmp2 = min(distfrn[1], distfrn[E[i].to] + E[i].scost + E[i].wcost + distto1[E[i].fr]); ans = min(ans, tmp + tmp2); } for (int i = 1; i <= m; i++) { if (!E[i].crit) continue; vector<ll> dist2fr1(n + 5, INF), dist2frn(n + 5, INF); dijk3(1, dist2fr1, i); dijk3(n, dist2frn, i); ans = min(ans, dist2fr1[n] + dist2frn[1] + E[i].scost); } if (ans == INF) ans = -1; cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...