제출 #888011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888011		oviyan_gandhi	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1097 ms	4948 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii; typedef vector<int> vi;

struct Edge {
    int u, v, c, d;
};

int n, m;
vector<multiset<pii>> adj;

int min_dist(int src, int dest){
    vi dist(n, -1);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : adj[u]){
            if (dist[v] == -1 || (d + w) < dist[v]){
                dist[v] = d + w;
                if (v != dest)
                    pq.push({dist[v], v});
            }
        }
    }
    return dist[dest];
}

int32_t main(){
    cin >> n >> m;
    adj.assign(n, multiset<pii>());
    vector<Edge> edges(m);
    for (auto &[u, v, c, d] : edges){
        cin >> u >> v >> c >> d;
        u--, v--;
        adj[u].insert({v, c});
    }
    int ans = -1;
    int fw = min_dist(0, n-1);
    if (fw != -1){
        int bw = min_dist(n-1, 0);
        if (bw != -1)
            ans = fw + bw;
    }
    for (auto [u, v, c, d] : edges){
        adj[u].erase(adj[u].find({v, c}));
        adj[v].insert({u, c});
        int fw = min_dist(0, n-1), bw;
        if (fw == -1)
            goto rollback;
        bw = min_dist(n-1, 0);
        if (bw == -1)
            goto rollback;
        if (ans == -1 || (fw + d + bw) < ans)
            ans = fw + d + bw;
rollback:
        adj[v].erase(adj[v].find({u, c}));
        adj[u].insert({v, c});
    }
    cout << ans << endl;
    return 0;
}

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