Submission #779551

#	Time	Username	Problem	Language	Result	Execution time	Memory
779551		1bin	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	33 ms	5672 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const ll inf = 1e18;
const int MX = 5e4 + 5;
ll n, m, a[MX], b[MX], c[MX], d[MX], ans, chk[2][MX], mnd[2], d1, d2, D[4][205];
vector<pair<ll, ll>> adj[205], rev[205];

ll dijk(int s, int e, int f){
    int t = n + 1 - s;
    vector<ll> dist(n + 1, inf);
    vector<int> E(n + 1, 0), vis(n + 1, 0);
    dist[s] = 0;
    while(1){
        ll mn = inf, x;
        for(int i = 1; i <= n; i++)
            if(!vis[i] && dist[i] < mn) mn = dist[i], x = i;
        if(mn == inf) break;
        vis[x] = 1;
        if(f == 1 || f == 3){
            for(auto&[nx, ix] : rev[x])
                if(ix != e && dist[x] + c[ix] < dist[nx]) dist[nx] = dist[x] + c[ix], E[nx] = ix;
        }
        else{
            for(auto&[nx, ix] : adj[x])
                if(ix != e && dist[x] + c[ix] < dist[nx]) dist[nx] = dist[x] + c[ix], E[nx] = ix;
        }
    }
    if(f >= 4){
        f -= 4;
        if(dist[t] == inf) return inf;
        for(int x = t; x != s; x = a[E[x]]) chk[f][E[x]] = 1;
    }
    else if(f >= 0) {
        for(int i = 1; i <= n; i++) D[f][i] = dist[i];
    }
    return dist[t];
}


int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        adj[a[i]].emplace_back(b[i], i);
        rev[b[i]].emplace_back(a[i], i);
    }
    dijk(1, -1, 0);
    dijk(n, -1, 1);
    dijk(n, -1, 2);
    dijk(1, -1, 3);
    mnd[0] = dijk(1, -1, 4);
    mnd[1] = dijk(n, -1, 5);
    ans = mnd[0] + mnd[1];
    for(int i = 0; i < m; i++){
        adj[b[i]].emplace_back(a[i], m);
        c[m] = c[i] + d[i];
        if(!chk[0][i]) d1 = min(mnd[0], D[0][b[i]] + c[i] + d[i] + D[1][a[i]]);
        else d1 = dijk(1, i, -1);
        if(!chk[1][i]) d2 = min(mnd[1], D[2][b[i]] + c[i] + d[i] + D[3][a[i]]);
        else d2 = dijk(n, i, -1);
        //cout << d1 << ' ' << d2 << '\n';
        ans = min(ans, d1 + d2);
        adj[b[i]].pop_back();
    }
    cout << (ans >= inf ? -1 : ans);
    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'll dijk(int, int, int)':
ho_t4.cpp:24:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |             for(auto&[nx, ix] : rev[x])
      |                      ^
ho_t4.cpp:28:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |             for(auto&[nx, ix] : adj[x])
      |                      ^

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