Submission #724868

#	Time	Username	Problem	Language	Result	Execution time	Memory
724868		Cookie	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	810 ms	9048 KiB

ho_t4

#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();
        if(dis[u][n] != dd)continue;
        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();
        if(dis[n][u] != dd)continue;
        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();
        if(dis[u][1] != dd)continue;
        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;
        }
    }
    
    int cnt = 0;
    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{
            cnt++;
            forr(j, 1, n + 1)d[j] = 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 == v){
                    if(d[u] > d[uu] + c){
                        d[u] = d[uu] + c; 
                        pq.push({d[u], u});
                    }
                }
            }
            ll curr = d[n];
            forr(j, 1, n + 1)d[j] = 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 == v){
                    if(d[u] > d[uu] + c){
                        d[u] = d[uu] + c; 
                        pq.push({d[u], u});
                    }
                } 
                
            }
            curr += d[1];
            ans = min(ans, curr + e);
        }
    }
    if(ans >= 1e18)cout << -1;
    else cout << ans;
    
    return(0);
}

Compilation message (stderr)

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:63:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |         for(auto [v, c, e, id]: rev[u]){
      |                  ^
ho_t4.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |         auto [dd, u] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:75:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |         for(auto [v, c, e, id]: adj[u]){
      |                  ^
ho_t4.cpp:86:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |         auto [dd, u] = pq.top(); pq.pop();
      |              ^
ho_t4.cpp:88:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |         for(auto [v, c, e, id]: rev[u]){
      |                  ^
ho_t4.cpp:115:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |         auto [u, v, c, e] = edge[i];
      |              ^
ho_t4.cpp:127:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |                 auto [dd, uu] = pq.top(); pq.pop();
      |                      ^
ho_t4.cpp:129:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |                 for(auto [vv, cc, ee, id]: adj[uu]){
      |                          ^
ho_t4.cpp:146:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  146 |                 auto [dd, uu] = pq.top(); pq.pop();
      |                      ^
ho_t4.cpp:148:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |                 for(auto [vv, cc, ee, id]: adj[uu]){
      |                          ^

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63