Submission #1106141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106141		Trisanu_Das	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1061 ms	4820 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second

vector<multiset<pair<int, int> > > adj;
vector<ll> sssp1, sssp2;

void dijkstra(int u, vector<ll>& sssp){
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    pq.push({sssp[u] = 0ll, u});
    while(!pq.empty()) {
        int x = pq.top().ss;
        pq.pop();
        for(auto [y, w] : adj[x])
            if(sssp[x] + w < sssp[y])
                pq.push({sssp[y] = sssp[x] + w, y});
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    adj.resize(n);
    vector<tuple<int, int, int, int> > edges;
    for(int i = 0; i < m; i++){
        int u, v, c, d; cin >> u >> v >> c >> d;
        u--; v--;
        adj[u].insert({v, c});
        edges.push_back(make_tuple(u, v, c, d));
    }
    sssp1 = sssp2 = vector<ll>(n, INT_MAX);
    dijkstra(0, sssp1);
    dijkstra(n - 1, sssp2);
    ll ans = min((ll)INT_MAX, sssp1[n - 1] + sssp2[0]);
    for(auto [u, v, c, d] : edges){
        adj[u].erase(adj[u].find({v, c}));
        adj[v].insert({u, c});
        sssp1 = sssp2 = vector<ll>(n, INT_MAX);
        dijkstra(0, sssp1);
        dijkstra(n - 1, sssp2);
        ans = min(ans, sssp1[n - 1] + sssp2[0] + d);
        adj[v].erase(adj[v].find({u, c}));
        adj[u].insert({v, c});
    }
    cout << (ans == INT_MAX ? -1 : ans) << '\n';
}

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