Submission #254384

#	Time	Username	Problem	Language	Result	Execution time	Memory
254384		Sorting	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	356 ms	4736 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

const int k_N = 200 + 3;
const int k_M = 5e4 + 3;
const long long k_Inf = 1e17;

int n, m;
long long dist[k_N][k_N];
array<int, 4> edges[k_M];

vector<array<int, 3>> adj[k_N], adj_rev[k_N];
long long d[k_N];
bool in_q[k_N];

bool f1_[k_M], f_n[k_M], f_1[k_M], fn_[k_M];
int par_edge[k_N];

void spfa(int from, int forbidden_idx, vector<array<int, 3>> *adj){
    queue<int> q;

    for(int i = 1; i <= n; ++i){
        d[i] = k_Inf;
        in_q[i] = false;
        par_edge[i] = -1;
    }

    d[from] = 0;
    q.push(from);
    in_q[from] = true;

    while(!q.empty()){
        int u = q.front();
        q.pop();
        in_q[u] = false;

        for(auto [to, cost, idx]: adj[u]){
            if(idx == forbidden_idx) continue;
            long long new_d = d[u] + cost;
            if(new_d < d[to]){
                d[to] = new_d;
                par_edge[to] = idx;
                if(!in_q[to]){
                    q.push(to);
                    in_q[to] = true;
                }
            }
        }
    }
}

void do_spfa(int from, bool rev, bool *arr){
    if(!rev) spfa(from, -1, adj);
    else spfa(from, -1, adj_rev);

    for(int i = 1; i <= n; ++i)
        if(par_edge[i] != -1)
            arr[par_edge[i]] = true; 
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            dist[i][j] = (i == j) ? 0 : k_Inf;

    for(int i = 0; i < m; ++i){
        array<int, 4> &e = edges[i];
        for(int j = 0; j < 4; ++j)
            cin >> e[j];
        dist[e[0]][e[1]] = min(dist[e[0]][e[1]], (long long)e[2]);

        adj[e[0]].push_back({e[1], e[2], i});
        adj_rev[e[1]].push_back({e[0], e[2], i});
    }

    do_spfa(1, false, f1_);
    do_spfa(1, true, f_1);
    do_spfa(n, false, fn_);
    do_spfa(n, true, f_n);

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            for(int k = 1; k <= n; ++k)
                if(dist[j][i] + dist[i][k] < dist[j][k])
                    dist[j][k] = dist[j][i] + dist[i][k];

    long long ans = k_Inf;
    ans = min(ans, dist[1][n] + dist[n][1]);

    for(int i = 0; i < m; ++i){


        auto [a, b, c, dd] = edges[i];
        long long curr = k_Inf;

        curr = min(curr, dist[1][n] + dist[n][b] + dist[a][1] + c + dd);
        curr = min(curr, dist[n][1] + dist[1][b] + dist[a][n] + c + dd);
        curr = min(curr, dist[n][b] + dist[a][1] + c + dist[1][b] + dist[a][n] + c + dd);

        if(curr < ans){
            long long _1n, _n1, _1b, _an, _nb, _a1;
            curr = k_Inf;

            if(f1_[i]){
                spfa(1, i, adj);
                _1n = d[n];
                _1b = d[b];
            }
            else{
                _1n = dist[1][n];
                _1b = dist[1][b];
            }

            if(fn_[i]){
                spfa(n, i, adj);
                _n1 = d[1];
                _nb = d[b];
            }
            else{
                _n1 = dist[n][1];
                _nb = dist[n][b];
            }

            if(f_n[i]){
                spfa(n, i, adj_rev);
                _an = d[a];
            }
            else _an = dist[a][n];

            if(f_1[i]){
                spfa(1, i, adj_rev);
                _a1 = d[a];
            }
            else _a1 = dist[a][1];

            curr = min(curr, _1n + _nb + _a1 + c + dd);
            curr = min(curr, _n1 + _1b + _an + c + dd);
            curr = min(curr, _nb + _a1 + c + _1b + _an + c + dd);

            //cout << curr << " - " << i << endl;

            ans = min(ans, curr);
        }
    }

    if(ans == k_Inf) ans = -1;
    cout << ans << "\n";
}

Compilation message (stderr)

ho_t4.cpp: In function 'void spfa(int, int, std::vector<std::array<int, 3> >*)':
ho_t4.cpp:38:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for(auto [to, cost, idx]: adj[u]){
                  ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:99:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [a, b, c, dd] = edges[i];
              ^

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