oj.uz

Submission #724867

# Submission time Handle Problem Language Result Execution time Memory
724867 2023-04-16T06:12:06 Z Cookie Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 25 ms 7264 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 + e);
        }
    }
    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 1 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 596 KB Output is correct
7 Correct 1 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 13 ms 724 KB Output is correct
11 Correct 17 ms 840 KB Output is correct
12 Incorrect 15 ms 724 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7212 KB Output is correct
2 Correct 25 ms 7092 KB Output is correct
3 Correct 23 ms 7072 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Incorrect 1 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 22 ms 5548 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 22 ms 6948 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 18 ms 7264 KB Output is correct
9 Correct 21 ms 7088 KB Output is correct
10 Correct 19 ms 7036 KB Output is correct
11 Correct 18 ms 6996 KB Output is correct
12 Correct 24 ms 7180 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 1 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 596 KB Output is correct
7 Correct 1 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 13 ms 724 KB Output is correct
11 Correct 17 ms 840 KB Output is correct
12 Incorrect 15 ms 724 KB Output isn't correct
13 Halted 0 ms 0 KB -