제출 #923129

#제출 시각아이디문제언어결과실행 시간메모리
923129CamillusOlympic Bus (JOI20_ho_t4)C++17
37 / 100
1038 ms6112 KiB
/// @author Camillus #include <bits/stdc++.h> #define int long long using ll = long long; using namespace std; int from[50'000]; int to[50'000]; int cost[50'000]; int change[50'000]; static constexpr int INF = 1e17; int n, m; vector<pair<int, int>> g[200]; int d_from[200]; int d_to[200]; void dist_from_all(int s) { for (int u = 0; u < n; u++) { g[u].resize(0); } for (int i = 0; i < m; i++) { g[to[i]].emplace_back(from[i], cost[i]); } auto d = d_to; for (int i = 0; i < n; i++) { d[i] = INF; } d[s] = 0; set<pair<int, int>> Q; Q.emplace(d[s], s); while (!Q.empty()) { int u = Q.begin()->second; Q.erase(Q.begin()); for (auto [v, c] : g[u]) { if (d[v] > d[u] + c) { Q.erase(pair(d[v], v)); d[v] = d[u] + c; Q.emplace(d[v], v); } } } } void dist_to_all(int s) { for (int u = 0; u < n; u++) { g[u].resize(0); } for (int i = 0; i < m; i++) { g[from[i]].emplace_back(to[i], cost[i]); } auto d = d_from; for (int i = 0; i < n; i++) { d[i] = INF; } d[s] = 0; set<pair<int, int>> Q; Q.emplace(d[s], s); while (!Q.empty()) { int u = Q.begin()->second; Q.erase(Q.begin()); for (auto [v, c] : g[u]) { if (d[v] > d[u] + c) { Q.erase(pair(d[v], v)); d[v] = d[u] + c; Q.emplace(d[v], v); } } } } int get_cost() { int result = 0; dist_to_all(0); dist_from_all(0); return min(INF, d_from[n - 1] + d_to[n - 1]); } random_device rd; mt19937_64 rnd(rd()); signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, c, d; cin >> u >> v >> c >> d; u--, v--; from[i] = u; to[i] = v; cost[i] = c; change[i] = d; } auto group1 = [&]() -> bool { return m <= 1000; }; auto group2 = [&]() -> bool { if (m % 2 == 1) { return false; } for (int i = 0; i < m; i += 2) { bool condition = from[i] == from[i + 1] && to[i] == to[i + 1] && cost[i] == cost[i + 1]; if (!condition) { return false; } } return true; }; auto group3 = [&]() -> bool { for (int i = 0; i < m; i++) { if (cost[i] != 0) { return false; } } return true; }; vector<vector<int>> d(n, vector<int>(n, INF)); vector<int> good; for (int i = 0; i < m; i++) { d[from[i]][to[i]] = min(d[from[i]][to[i]], cost[i]); } for (int u = 0; u < n; u++) { d[u][u] = 0; } for (int k = 0; k < n; k++) { for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { d[u][v] = min(d[u][v], d[u][k] + d[k][v]); } } } vector<int> best1(m); iota(best1.begin(), best1.end(), 0); sort(best1.begin(), best1.end(), [&](int i, int j) -> bool { auto val = [&](int x) -> int { return d[0][to[x]] + cost[x] + change[x] + d[from[x]][n - 1]; }; return val(i) < val(j); }); best1.resize(min(best1.size(), (size_t)300)); vector<int> best2(m); iota(best2.begin(), best2.end(), 0); sort(best2.begin(), best2.end(), [&](int i, int j) -> bool { auto val = [&](int x) -> int { return d[n - 1][to[x]] + cost[x] + change[x] + d[from[x]][0]; }; return val(i) < val(j); }); best2.resize(min(best2.size(), (size_t)300)); vector<int> best; for (int i : best1) { best.push_back(i); } for (int i : best2) { best.push_back(i); } sort(best.begin(), best.end()); best.erase(unique(best.begin(), best.end()), best.end()); int initial = get_cost(); int ans = initial; for (int i : best) { swap(from[i], to[i]); ans = min(ans, get_cost() + change[i]); swap(from[i], to[i]); } cout << (ans == INF ? -1 : ans) << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'long long int get_cost()':
ho_t4.cpp:86:9: warning: unused variable 'result' [-Wunused-variable]
   86 |     int result = 0;
      |         ^~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:113:10: warning: variable 'group1' set but not used [-Wunused-but-set-variable]
  113 |     auto group1 = [&]() -> bool {
      |          ^~~~~~
ho_t4.cpp:117:10: warning: variable 'group2' set but not used [-Wunused-but-set-variable]
  117 |     auto group2 = [&]() -> bool {
      |          ^~~~~~
ho_t4.cpp:132:10: warning: variable 'group3' set but not used [-Wunused-but-set-variable]
  132 |     auto group3 = [&]() -> bool {
      |          ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...