oj.uz

Submission #724866

# Submission time Handle Problem Language Result Execution time Memory
724866 2023-04-16T06:11:27 Z Cookie Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 30 ms 8072 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define ll long long
#define int long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const ll mod = 1e9 + 7;
const int mxn = 205, mxm = 50005;
struct E{
     ll v, c, e, id;
};
ll d[mxn + 1];
vt<E>adj[mxn + 1], rev[mxn + 1];
E edge[mxm + 1];
bool used[mxm + 1];
pii trace[mxn + 1], trace2[mxn + 1];
int n, m;
ll dis[205][205];
signed main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    forr(i, 1, n + 1){
        forr(j, 1, n + 1){
            dis[i][j] = 1e18;
        }
    }
    forr(i, 0, m){
        int u, v, c, e; cin >> u >> v >> c >> e;
        adj[u].pb({v, c, e, i}); rev[v].pb({u, c, e, i});
        edge[i] = {u, v, c, e};
    }
    dis[1][1] = 0;
    priority_queue<pll, vt<pll>, greater<pll>>pq; pq.push({dis[1][1], 1});
    while(!pq.empty()){
        auto [dd, u] = pq.top(); pq.pop();
        if(dis[1][u] != dd)continue;
        for(auto [v, c, e, id]: adj[u]){
            if(dis[1][v] > dis[1][u] + c){
                dis[1][v] = dis[1][u] + c;
                pq.push({dis[1][v], v});
                trace[v] = make_pair(id, u);
            }
        }
    }
    dis[n][n] = 0;
    pq.push({dis[n][n], n});
    while(!pq.empty()){
        auto [dd, u] = pq.top(); pq.pop();
        for(auto [v, c, e, id]: rev[u]){
            if(dis[v][n] > dis[u][n] + c){
                dis[v][n] = dis[u][n] + c;
                pq.push({dis[v][n], v});
            }
        }
        
    }
    pq.push({dis[n][n], n});
    while(!pq.empty()){
        auto [dd, u] = pq.top(); pq.pop();
        for(auto [v, c, e, id]: adj[u]){
            if(dis[n][v] > dis[n][u] + c){
                dis[n][v] = dis[n][u] + c;
                pq.push({dis[n][v], v});
                trace2[v] = make_pair(id, u);
            }
        }
    }
    
    pq.push({dis[1][1], 1});
    while(!pq.empty()){
        auto [dd, u] = pq.top(); pq.pop();
        for(auto [v, c, e, id]: rev[u]){
            if(dis[v][1] > dis[u][1] + c){
                dis[v][1] = dis[u][1] + c;
                pq.push({dis[v][1], v});
            }
        }
    }
    
    if(dis[1][n] < 1e18){
        int v = n;
        while(v != 1){
            used[trace[v].fi] = 1;
            v = trace[v].se;
        }
    }
    
    if(dis[n][1] < 1e18){
        int v = 1;
        while(v != n){
            used[trace2[v].fi] = 1;
            v = trace2[v].se;
        }
    }
    
    
    ll ans = dis[1][n] + dis[n][1];
    for(int i = 0; i < m; i++){
        auto [u, v, c, e] = edge[i];
        if(!used[i]){
            
            ll ton = min(dis[1][n], dis[1][v] + dis[u][n] + c);
            ll to1 = min(dis[n][1], dis[n][v] + dis[u][1] + c);
            ans = min(ans, ton + to1 + e);
            
        }else{
            forr(i, 1, n + 1)d[i] = 1e18;
            d[1] = 0; pq.push({d[1], 1});
            while(!pq.empty()){
                auto [dd, uu] = pq.top(); pq.pop();
                if(d[uu] != dd)continue;
                for(auto [vv, cc, ee, id]: adj[uu]){
                    if(id == i)continue;
                    if(d[vv] > d[uu] + cc){
                        d[vv] = d[uu] + cc; pq.push({d[vv], vv});
                    }
                }
                if(uu == u){
                    if(d[v] > d[uu] + c){
                        d[v] = d[uu] + c; 
                        pq.push({d[v], v});
                    }
                }
            }
            ll curr = d[n];
            forr(i, 1, n + 1)d[i] = 1e18;
            d[n] = 0; pq.push({d[n], n});
            while(!pq.empty()){
                auto [dd, uu] = pq.top(); pq.pop();
                if(d[uu] != dd)continue;
                for(auto [vv, cc, ee, id]: adj[uu]){
                    if(id == i)continue;
                    if(d[vv] > d[uu] + cc){
                        d[vv] = d[uu] + cc; pq.push({d[vv], vv});
                    }
                }
                if(uu == u){
                    if(d[v] > d[uu] + c){
                        d[v] = d[uu] + c; 
                        pq.push({d[v], v});
                    }
                }
            }
            curr += d[1];
            ans = min(ans, curr);
        }
    }
    if(ans >= 1e18)cout << -1;
    else cout << ans;
    
    return(0);
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         auto [dd, u] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:50:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |         for(auto [v, c, e, id]: adj[u]){
      |                  ^
ho_t4.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         auto [dd, u] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:62:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |         for(auto [v, c, e, id]: rev[u]){
      |                  ^
ho_t4.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |         auto [dd, u] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:73:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |         for(auto [v, c, e, id]: adj[u]){
      |                  ^
ho_t4.cpp:84:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |         auto [dd, u] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:85:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         for(auto [v, c, e, id]: rev[u]){
      |                  ^
ho_t4.cpp:112:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |         auto [u, v, c, e] = edge[i];
      |              ^
ho_t4.cpp:123:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |                 auto [dd, uu] = pq.top(); pq.pop();
      |                      ^
ho_t4.cpp:125:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |                 for(auto [vv, cc, ee, id]: adj[uu]){
      |                          ^
ho_t4.cpp:142:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  142 |                 auto [dd, uu] = pq.top(); pq.pop();
      |                      ^
ho_t4.cpp:144:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  144 |                 for(auto [vv, cc, ee, id]: adj[uu]){
      |                          ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 12 ms 832 KB Output is correct
11 Correct 16 ms 724 KB Output is correct
12 Incorrect 15 ms 836 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7152 KB Output is correct
2 Correct 30 ms 6988 KB Output is correct
3 Correct 23 ms 7088 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 18 ms 5460 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 19 ms 6996 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 26 ms 7256 KB Output is correct
9 Correct 19 ms 8044 KB Output is correct
10 Correct 19 ms 7980 KB Output is correct
11 Correct 19 ms 7780 KB Output is correct
12 Correct 23 ms 8072 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 12 ms 832 KB Output is correct
11 Correct 16 ms 724 KB Output is correct
12 Incorrect 15 ms 836 KB Output isn't correct
13 Halted 0 ms 0 KB -