Submission #1277544

#TimeUsernameProblemLanguageResultExecution timeMemory
1277544minggaOlympic Bus (JOI20_ho_t4)C++20
0 / 100
15 ms2576 KiB
// Author: caption_mingle #include "bits/stdc++.h" using namespace std; #define ln "\n" #define pb push_back #define fi first #define se second #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define ll long long const int mod = 1e9 + 7; const int inf = 2e9; const int N = 205; const int M = 50005; int n, m, d[5][N], p[N]; pair<int, int> trace[N]; bool mark[M]; struct edge { int u, v, c, d; } ed[M]; vector<pair<int, int>> g[2][N]; void dijkstra(int id, int st) { for(int i = 1; i <= n; i++) p[i] = 0, d[id][i] = inf; d[id][st] = 0; d[id][0] = inf; trace[st] = {0, 0}; int eid = (id >> 1) & 1; for(int i = 1; i <= n; i++) { int u = 0; for(int j = 1; j <= n; j++) { if(!p[j] && d[id][j] < d[id][u]) { u = j; } } for(auto [v, x] : g[eid][u]) { if(d[id][v] > d[id][u] + ed[x].c) { d[id][v] = d[id][u] + ed[x].c; trace[v] = {x, u}; } } p[u] = 1; } int en = st == 1 ? n : 1; while(en) { mark[trace[en].fi] = 1; en = trace[en].se; } } int calc_dist(int st, int en) { vector<int> dist(n + 1, inf); for(int i = 1; i <= n; i++) p[i] = 0; p[st] = 1; dist[st] = 0; for(int i = 1; i <= n; i++) { int u = 0; for(int j = 1; j <= n; j++) { if(p[j] && dist[j] < dist[u]) { u = j; } } for(auto [v, x] : g[0][u]) { if(dist[v] > dist[u] + ed[x].c) { dist[v] = dist[u] + ed[x].c; } } } return dist[en]; } signed main() { cin.tie(0) -> sync_with_stdio(0); #define task "" if(fopen(task ".INP", "r")) { freopen(task ".INP", "r", stdin); freopen(task ".OUT", "w", stdout); } cin >> n >> m; for(int i = 1; i <= m; i++) { int u, v, c, d; cin >> u >> v >> c >> d; ed[i] = {u, v, c, d}; g[0][u].pb({v, i}); g[1][v].pb({u, i}); } dijkstra(0, 1); dijkstra(1, n); dijkstra(2, 1); dijkstra(3, n); ll ans = 1ll * d[0][n] + d[1][1]; for(int i = 1; i <= m; i++) { int u = ed[i].u, v = ed[i].v, c = ed[i].c, dd = ed[i].d; // cerr << i << ' ' << mark[i] << ' '; if(mark[i]) { g[0][u].erase(find(all(g[0][u]), make_pair(v, i))); g[0][v].pb({u, i}); ans = min(ans, 1ll * calc_dist(1, n) + 1ll * calc_dist(n, 1) + dd); g[0][u].pb({v, i}); g[0][v].pop_back(); // cerr << 1ll * calc_dist(1, n) + calc_dist(n, 1) + dd; } else { ll d1n = min(d[0][n], d[0][v] + d[3][u] + c); ll dn1 = min(d[1][1], d[1][v] + d[2][u] + c); ans = min(ans, d1n + dn1 + dd); // cerr << d1n + dn1 + dd; } // cerr << ln; } if(ans >= inf) ans = -1; cout << ans << ln; cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC; }

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:80:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:81:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...