제출 #1326200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326200		ivan_alexeev	Olympic Bus (JOI20_ho_t4)	C++20	37 / 100	1094 ms	44008 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#ifndef lisie_bimbi
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
#endif

using ll = long long;
const ll inf = 1'000'000'000;

#define int unsigned

struct edge{
    int u;
    int c;
    int ind;
    edge(int a, int b, int c1){
        u = a;
        c = b;
        ind = c1;
    }
};

int n;
vector<vector<edge>> v, v1;


vector<int> dij(int start, vector<vector<edge>> &g){
    vector<int> d(n, inf);
    d[start] = 0;
    set<pair<int, int>> q;
    for(int i = 0; i < n; i++){
        q.insert({d[i], i});
    }
    while(!q.empty()){
        auto [dd, u] = *q.begin();
        q.erase(q.begin());
        for(auto [i, j, ind] : g[u]){
            if(dd + j < d[i]){
                q.erase({d[i], i});
                d[i] = dd + j;
                q.insert({d[i], i});
            }
        }
    }
    return d;
}

vector<int> dij_ban(int start, int ban, vector<vector<edge>> &g){
    vector<int> d(n, inf);
    d[start] = 0;
    set<pair<int, int>> q;
    for(int i = 0; i < n; i++){
        q.insert({d[i], i});
    }
    while(!q.empty()){
        auto [dd, u] = *q.begin();
        q.erase(q.begin());
        if(u == ban){
            continue;
        }
        for(auto [i, j, ind] : g[u]){
            if(dd + j < d[i]){
                q.erase({d[i], i});
                d[i] = dd + j;
                q.insert({d[i], i});
            }
        }
    }
    d[ban] = inf;
    return d;
}


void solve(){
    int m;
    cin >> n >> m;
    n += 2;
    v.resize(n);
    v1.resize(n);
    vector<array<int, 4>> z;
    for(int i = 0; i < m; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        v[a].emplace_back(b, c, i);
        v1[b].emplace_back(a, c, i);
        z.push_back({a, b, c, d});
    }
    v[0].emplace_back(1, 0, m);
    v[1].emplace_back(0, 0, m + 1);
    v1[0].emplace_back(1, 0, m + 1);
    v1[1].emplace_back(0, 0, m);
    z.push_back({0, 1, 0, 0});
    z.push_back({1, 0, 0, 0});
    v[n - 1].emplace_back(n - 2, 0, m + 2);
    v[n - 2].emplace_back(n - 1, 0, m + 3);
    v1[n - 1].emplace_back(n - 2, 0, m + 3);
    v1[n - 2].emplace_back(n - 1, 0, m + 2);
    z.push_back({n - 1, n - 2, 0, 0});
    z.push_back({n - 2, n - 1, 0, 0});
    m += 4;
    vector<vector<int>> dist(n, vector<int>(n, inf));
    for(auto i : z){
        dist[i[0]][i[1]] = min(dist[i[0]][i[1]], i[2]);
    }
    for(int i = 0; i < n; i++){
        dist[i][i] = 0;
    }
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    vector<vector<int>> without0(n), withoutn(n), without01(n), withoutn1(n);
    for(int i = 0; i < n; i++){
        without0[i] = dij_ban(0, i, v);
        without01[i] = dij_ban(0, i, v1);
        withoutn[i] = dij_ban(n - 1, i, v);
        withoutn1[i] = dij_ban(n - 1, i, v1);
    }
    int ans = inf;
    ans = min(ans, dist[0][n - 1] + dist[n - 1][0]);
    vector<vector<int>> vans1(n), vans2(n);
    vector<pair<int, int>> ANS1(n, {inf, inf}), ANS2(n, {inf, inf});
    for(int b = 0; b < n; b++){
        vans1[b].resize(v[b].size());
        for(int ind = 0; ind < v[b].size(); ind++){
            auto [i, j, ind1] = v[b][ind];
            if(i == b){
                continue;
            }
            vans1[b][ind] = j + withoutn1[b][i];
            if(vans1[b][ind] < ANS1[b].first){
                ANS1[b].second = ANS1[b].first;
                ANS1[b].first = vans1[b][ind];
            }else if(vans1[b][ind] < ANS1[b].second){
                ANS1[b].second = vans1[b][ind];
            }
        }
        vans2[b].resize(v[b].size());
        for(int ind = 0; ind < v[b].size(); ind++){
            auto [i, j, ind1] = v[b][ind];
            if(i == b){
                continue;
            }
            vans2[b][ind] = j + without01[b][i];
            if(vans2[b][ind] < ANS2[b].first){
                ANS2[b].second = ANS2[b].first;
                ANS2[b].first = vans2[b][ind];
            }else if(vans2[b][ind] < ANS2[b].second){
                ANS2[b].second = vans2[b][ind];
            }
        }
    }
    vector<vector<int>> piske(n, vector<int>(m, -1));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < v[i].size(); j++){
            piske[i][v[i][j].ind] = j;
        }
    }
    for(int ind = 0; ind < z.size(); ind++){
        auto [b, a, c, dd] = z[ind];
        if(a == b){
            continue;
        }
        int cost = min(c, dist[a][b]);
        int ans1 = inf;
        // cout << "aaaaaaaa " << b << ' ' << a << ' ' << c << ' ' << dd << endl;
        ans1 = min(ans1, without0[b][a] + cost + withoutn1[a][b]);
        ans1 = min(ans1, without0[b][n - 1]);
        ans1 = min(ans1, without0[a][n - 1]);
        int popa = piske[b][ind];
        int mn1 = inf;
        if(vans1[b][popa] == ANS1[b].first){
            mn1 = ANS1[b].second;
        }else{
            mn1 = ANS1[b].first;
        }
        ans1 = min(ans1, without0[a][b] + mn1);
        
        int ans2 = inf;
        ans2 = min(ans2, withoutn[b][a] + cost + without01[a][b]);
        ans2 = min(ans2, withoutn[b][0]);
        ans2 = min(ans2, withoutn[a][0]);
        int mn2 = inf;
        if(vans2[b][popa] == ANS2[b].first){
            mn2 = ANS2[b].second;
        }else{
            mn2 = ANS2[b].first;
        }
        ans2 = min(ans2, withoutn[a][b] + mn2);
        ans = min(ans, ans1 + ans2 + dd);
        // cout << ans1 << ' ' << ans2 << ' ' << dd << endl;
    }
    if(ans >= inf){
        cout << -1 << endl;
        return; 
    }
    cout << ans << endl;
}

signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
#endif
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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