제출 #632410

#제출 시각아이디문제언어결과실행 시간메모리
632410colossal_pepeOlympic Bus (JOI20_ho_t4)C++17
37 / 100
1034 ms3788 KiB
#include <iostream> #include <vector> #include <set> #include <tuple> #include <cstring> using namespace std; using ll = long long; const ll INF = 1e16; int n, m; vector<tuple<int, int, ll, ll>> edges; vector<vector<int>> g; vector<vector<ll>> d; set<int> imp_edges; ll ssp(int start, int end, int flipped) { ll d[n]; for (int i = 0; i < n; i++) { d[i] = INF; } bool vis[n]; memset(vis, 0, sizeof vis); d[start] = 0; for (int _ = 0; _ < n; _++) { int u = -1; for (int i = 0; i < n; i++) { if (not vis[i] and (u == -1 or d[i] < d[u])) u = i; } for (int i : g[u]) { auto [a, b, w, c] = edges[i]; if (flipped == i) swap(a, b); d[b] = min(d[b], d[u] + w); } vis[u] = 1; } return d[end]; } void restoreEdges(int u, int start, bool vis[]) { vis[u] = 1; for (int i : g[u]) { auto [a, b, w, c] = edges[i]; if (not vis[b] and d[start][b] == d[start][u] + w) { imp_edges.insert(i); restoreEdges(b, start, vis); } } } void getImpEdges() { bool vis[n]; memset(vis, 0, sizeof vis); restoreEdges(0, 0, vis); memset(vis, 0, sizeof vis); restoreEdges(n - 1, n - 1, vis); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; g.resize(n), edges.resize(m); d.resize(n, vector<ll>(n, INF)); for (int i = 0; i < n; i++) { d[i][i] = 0; } for (int i = 0; i < m; i++) { auto &[a, b, w, c] = edges[i]; cin >> a >> b >> w >> c; a--, b--; g[a].push_back(i); g[b].push_back(i); d[a][b] = min(d[a][b], w); } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } getImpEdges(); // cout << "DUCK : " << endl; // for (int i = 0; i < n; i++) { // for (int j = 0; j < n; j++) { // cout << d[i][j] << ' '; // } // cout << endl; // } // cout << "FUCK : "; // for (int i : imp_edges) { // cout << i << ' '; // } // cout << endl; ll ans = d[0][n - 1] + d[n - 1][0]; // 0 0 for (int i = 0; i < m; i++) { auto [a, b, w, c] = edges[i]; if (imp_edges.find(i) != imp_edges.end()) { ans = min(ans, ssp(0, n - 1, i) + ssp(n - 1, 0, i) + c); continue; } ans = min(ans, d[0][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 0 1 ans = min(ans, d[0][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 0 2 ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][0] + c); // 1 0 ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 1 1 ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 1 2 ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][0] + c); // 2 0 ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 2 1 ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 2 2 } cout << (ans < INF ? ans : -1) << '\n'; 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...