Submission #824985

#	Time	Username	Problem	Language	Result	Execution time	Memory
824985		phoenix	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	172 ms	4092 KiB

ho_t4

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1000;
const int M = 100000;
const ll INF = 1e18;

int n, m;
vector<pair<int, int>> g[2][N];
ll C[M], D[M];
pair<int, int> edges[M];

vector<vector<ll>> dist, par;

vector<ll> dijkstra(int s, int b, bool save = 0) {
    vector<ll> d(n + 1, INF);
    vector<ll> p(n + 1, -1);
    d[s] = 0;
    bool processed[n + 1] = {};
    while(1) {
        s = -1;
        for(int i = 1; i <= n; i++) {
            if(processed[i]) continue;
            if(s == -1 || d[s] > d[i]) 
                s = i;
        }
        if(s == -1) break;
        processed[s] = 1;

        for(auto [to, i] : g[b][s]) {
            if(d[to] > d[s] + C[i]) {
                p[to] = i;
                d[to] = d[s] + C[i];
            }
        }
    }
    if(save) {
        dist.push_back(d);
        par.push_back(p);
    }
    return d;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        cin >> C[i] >> D[i];
        g[0][u].push_back({v, i});
        g[1][v].push_back({u, i});
    }
    dijkstra(1, 0, 1);
    dijkstra(n, 0, 1);
    dijkstra(1, 1, 1);
    dijkstra(n, 1, 1);
    int cur = n;
    set<int> way1, way2;
    while(par[0][cur] != -1) {
        way1.insert(par[0][cur]);
        cur = edges[par[0][cur]].first;
    }
    if(cur != 1) way1.clear();
    cur = 1;
    while(par[1][cur] != -1) {
        way2.insert(par[1][cur]);
        cur = edges[par[1][cur]].first;
    }
    if(cur != n) way2.clear();
    ll res = dist[0][n] + dist[1][1];

    for(int i = 0; i < m; i++) {
        ll ans = INF;
        auto [u, v] = edges[i];
        
        if(!way1.count(i) && !way2.count(i)) {
            ans = min(ans, dist[1][v] + dist[2][u] + dist[0][n] + C[i] + D[i]);
            ans = min(ans, dist[0][v] + dist[3][u] + dist[1][1] + C[i] + D[i]);
            ans = min(ans, dist[0][v] + dist[3][u] + dist[1][v] + dist[2][u] + 2 * C[i] + D[i]);
        }
        else {
            g[0][u].erase(find(g[0][u].begin(), g[0][u].end(), make_pair(v, i)));
            g[0][v].push_back({u, i});
            
            auto d1 = dijkstra(1, 0), d2 = dijkstra(n, 0);
            ans = min(ans, d1[n] + d2[1] + D[i]);
            g[0][u].push_back({v, i});
            g[0][v].erase(find(g[0][v].begin(), g[0][v].end(), make_pair(u, i)));
        }
        res = min(res, ans);
    }
    if(res >= INF) res = -1;
    cout << res;
}

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