제출 #1106147

#제출 시각아이디문제언어결과실행 시간메모리
1106147Trisanu_DasOlympic Bus (JOI20_ho_t4)C++17
32 / 100
28 ms4176 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1 << 9, M = 1 << 16; const ll inf = 1e18; int n; ll d[N][N], dist[N]; int a[M], b[M], w[M], c[M]; vector<int> g[N]; bool vis[N]; ll dij(int s, int t) { fill(dist, dist + n + 1, inf); fill(vis, vis + n, false); dist[s] = 0; for (int i = 0; i < n; ++i) { int u = n; for (int v = 0; v < n; ++v) if (!vis[v] && dist[v] < dist[u]) u = v; vis[u] = true; if (dist[u] == inf) break; for (int e : g[u]) dist[b[e]] = min(dist[b[e]], dist[u] + w[e]); } return dist[t]; } int main() { cin.tie(nullptr)->sync_with_stdio(false); int m; cin >> n >> m; for (int u = 0; u < n; ++u) for (int v = 0; v < n; ++v) d[u][v] = inf; for (int u = 0; u < n; ++u) d[u][u] = 0; for (int e = 0; e < m; ++e) { cin >> a[e] >> b[e] >> w[e] >> c[e]; --a[e]; --b[e]; d[a[e]][b[e]] = min(d[a[e]][b[e]], (ll)w[e]); g[a[e]].push_back(e); } for (int w = 0; w < n; ++w) for (int u = 0; u < n; ++u) for (int v = 0; v < n; ++v) d[u][v] = min(d[u][v], d[u][w] + d[w][v]); int s = 0, t = n - 1; ll ans = d[s][t] + d[t][s]; for (int e = 0; e < m; ++e) { ll to = min(d[s][t], d[s][b[e]] + w[e] + d[a[e]][t]); ll fr = min(d[t][s], d[t][b[e]] + w[e] + d[a[e]][s]); if (c[e] + to + fr < ans) { g[a[e]].erase(find(g[a[e]].begin(), g[a[e]].end(), e)); swap(a[e], b[e]); g[a[e]].push_back(e); bool flag = (dij(s, t) < inf) && (dij(t, s) < inf); if (flag) ans = min(ans, c[e] + to + fr); g[a[e]].pop_back(); swap(a[e], b[e]); g[a[e]].push_back(e); } } cout << (ans < inf ? ans : -1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...