제출 #201504

#제출 시각아이디문제언어결과실행 시간메모리
201504Noam527Olympic Bus (JOI20_ho_t4)C++17
5 / 100
63 ms3684 KiB
#include <bits/stdc++.h> #define finish(x) return cout << x << endl, 0 typedef long long ll; typedef long double ldb; const int md = 1e9 + 7; const ll inf = 4e16; const int OO = 0; const int OOO = 1; using namespace std; struct edge { int v, w, i; edge() {} edge(int vv, int ww, int ii) { v = vv; w = ww; i = ii; } bool operator < (const edge &a) const { return w > a.w; } }; int n, m; vector<pair<int, int>> e; vector<int> c, d; vector<vector<edge>> g; vector<ll> cost; vector<int> dist, to; vector<int> path1, path2; vector<int> P1, P2; // P1[i] == j if edge i is used as the jth edge (1-indexed), 0 otherwise // floyd warshall; normal, without p1, without p2 int fw[202][202], fwp1[202][202], fwp2[202][202]; vector<int> dijkstra(int s, int t) { for (auto &i : dist) i = -1; priority_queue<edge> q; q.push(edge(s, 0, -1)); while (q.size()) { edge x = q.top(); q.pop(); if (dist[x.v] != -1) continue; dist[x.v] = x.w; to[x.v] = x.i; for (const auto &i : g[x.v]) if (dist[i.v] == -1) q.push(edge(i.v, x.w + i.w, i.i)); } if (dist[t] == -1) return{}; vector<int> res; int cur = t; while (cur != s) { res.push_back(to[cur]); cur = e[to[cur]].first; } reverse(res.begin(), res.end()); return res; } int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> m; e.resize(m), c.resize(m), d.resize(m); g.resize(n); cost.resize(m, 0); dist.resize(n), to.resize(n); P1.resize(m, 0), P2.resize(m, 0); for (int i = 0; i < m; i++) { cin >> e[i].first >> e[i].second >> c[i] >> d[i]; e[i].first--, e[i].second--; g[e[i].first].push_back(edge(e[i].second, c[i], i)); } path1 = dijkstra(0, n - 1), path2 = dijkstra(n - 1, 0); for (int i = 0; i < path1.size(); i++) P1[path1[i]] = i + 1; for (int i = 0; i < path2.size(); i++) P2[path2[i]] = i + 1; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (i != j) fw[i][j] = fwp1[i][j] = fwp2[i][j] = md; else fw[i][j] = fwp1[i][j] = fwp2[i][j] = 0; } for (int i = 0; i < m; i++) { fw[e[i].first][e[i].second] = min(fw[e[i].first][e[i].second], c[i]); if (!P1[i]) fwp1[e[i].first][e[i].second] = min(fwp1[e[i].first][e[i].second], c[i]); if (!P2[i]) fwp2[e[i].first][e[i].second] = min(fwp2[e[i].first][e[i].second], c[i]); } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { fw[i][j] = min(fw[i][j], fw[i][k] + fw[k][j]); fwp1[i][j] = min(fwp1[i][j], fwp1[i][k] + fwp1[k][j]); fwp2[i][j] = min(fwp2[i][j], fwp2[i][k] + fwp2[k][j]); } if (OO) { cout << "fw\n"; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << fw[i][j] << " "; cout << '\n'; } cout << "fwp1\n"; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << fwp1[i][j] << " "; cout << '\n'; } cout << "fwp2\n"; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << fwp2[i][j] << " "; cout << '\n'; } cout << "path1:\n"; for (const auto &i : path1) cout << i << " "; cout << '\n'; cout << "path2:\n"; for (const auto &i : path2) cout << i << " "; cout << '\n'; } // costs for path 1 for (int i = 0; i < m; i++) { int u = e[i].first, v = e[i].second; if (!P1[i]) { if (fw[0][v] == md || fw[u][n - 1] == md) { if (fw[0][n - 1] == md) cost[i] += inf; else cost[i] += fw[0][n - 1]; } else if (fw[0][n - 1] == md) cost[i] += fw[0][v] + c[i] + fw[u][n - 1]; else cost[i] += min(fw[0][n - 1], fw[0][v] + c[i] + fw[u][n - 1]); } else { int best = md; for (int l = 0; l < P1[i]; l++) for (int r = P1[i]; r < path1.size(); r++) { u = e[path1[l]].first, v = e[path1[r - 1]].second; if (fw[0][u] != md && fwp1[u][v] != md && fw[v][n - 1] != md) best = min(best, fw[0][u] + fwp1[u][v] + fw[v][n - 1]); } if (best == md) cost[i] += inf; else cost[i] += best; } } // same thing for path 2 for (int i = 0; i < m; i++) { int u = e[i].first, v = e[i].second; if (!P2[i]) { if (fw[n - 1][v] == md || fw[u][0] == md) { if (fw[n - 1][0] == md) cost[i] += inf; else cost[i] += fw[n - 1][0]; } else if (fw[n - 1][0] == md) cost[i] += fw[n - 1][v] + c[i] + fw[u][0]; else cost[i] += min(fw[n - 1][0], fw[n - 1][v] + c[i] + fw[u][0]); } else { int best = md; for (int l = 0; l < P2[i]; l++) for (int r = P2[i]; r < path2.size(); r++) { u = e[path2[l]].first, v = e[path2[r - 1]].second; if (fw[n - 1][u] != md && fwp2[u][v] != md && fw[v][0] != md) best = min(best, fw[n - 1][u] + fwp2[u][v] + fw[v][0]); } if (best == md) cost[i] += inf; else cost[i] += best; } } ll ans = inf; if (fw[0][n - 1] != md && fw[n - 1][0] != md) ans = min(ans, (ll)fw[0][n - 1] + fw[n - 1][0]); for (int i = 0; i < m; i++) ans = min(ans, cost[i] + d[i]); if (ans > 2 * md) cout << "-1\n"; else cout << ans << '\n'; }

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

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < path1.size(); i++)
                  ~~^~~~~~~~~~~~~~
ho_t4.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < path2.size(); i++)
                  ~~^~~~~~~~~~~~~~
ho_t4.cpp:106:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << fw[i][j] << " "; cout << '\n';
    ^~~
ho_t4.cpp:106:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int j = 0; j < n; j++) cout << fw[i][j] << " "; cout << '\n';
                                                         ^~~~
ho_t4.cpp:110:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << fwp1[i][j] << " "; cout << '\n';
    ^~~
ho_t4.cpp:110:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int j = 0; j < n; j++) cout << fwp1[i][j] << " "; cout << '\n';
                                                           ^~~~
ho_t4.cpp:114:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int j = 0; j < n; j++) cout << fwp2[i][j] << " "; cout << '\n';
    ^~~
ho_t4.cpp:114:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for (int j = 0; j < n; j++) cout << fwp2[i][j] << " "; cout << '\n';
                                                           ^~~~
ho_t4.cpp:117:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : path1) cout << i << " "; cout << '\n';
   ^~~
ho_t4.cpp:117:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : path1) cout << i << " "; cout << '\n';
                                                 ^~~~
ho_t4.cpp:119:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : path2) cout << i << " "; cout << '\n';
   ^~~
ho_t4.cpp:119:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : path2) cout << i << " "; cout << '\n';
                                                 ^~~~
ho_t4.cpp:139:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int l = 0; l < P1[i]; l++) for (int r = P1[i]; r < path1.size(); r++) {
                                                        ~~^~~~~~~~~~~~~~
ho_t4.cpp:168:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int l = 0; l < P2[i]; l++) for (int r = P2[i]; r < path2.size(); r++) {
                                                        ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...