Submission #758683

#	Time	Username	Problem	Language	Result	Execution time	Memory
758683		jasmin	Olympic Bus (JOI20_ho_t4)	C++17	32 / 100	623 ms	8212 KiB

ho_t4

#include<bits/stdc++.h>

#define int long long

using namespace std;

void dijkstra(vector<set<tuple<int,int,int>>>& adj, vector<long long>& dist, int start, vector<int>&parent){
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dist[start] = 0;
    pq.push({0,start});
    while(!pq.empty()){
        int wo = pq.top().second, preis = pq.top().first;
        pq.pop();
        if(dist[wo]== preis){
            for(tuple<int,int,int> next: adj[wo]){
                auto [ziel, kosten, umdrehkosten] = next;
                if(dist[ziel] > preis+kosten){
                    dist[ziel] = preis+kosten;
                    parent[ziel] = wo;
                    pq.push({dist[ziel], ziel});
                }
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int v, e; cin >> v >> e;
    vector<set<tuple<int,int,int>>>adj(v), adj2(v);
    vector<tuple<int,int,int,int>> edges(e);
    for(int i=0; i<e; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        a--; b--;
        adj[a].insert(make_tuple(b,c,d));
        adj2[b].insert(make_tuple(a,c,d));//umgedrehter Graph
        edges[i] = make_tuple(a,b,c,d);
    }
    vector<long long> von0(v, 1e17), parent0(v, -1), vonn_r(v, 1e17), parent2(v, -1), vonn(v, 1e17), parentn(v, -1), von0_r(v, 1e17);
    dijkstra(adj, von0, 0, parent0);
    dijkstra(adj2, vonn_r, v-1, parent2);
    dijkstra(adj2, von0_r, 0, parent2);
    dijkstra(adj, vonn, v-1, parentn);
    map<int,pair<int,int>> in_shortest_path;
    int ort = v-1;
    while(parent0[ort]!=-1){
        in_shortest_path[parent0[ort]] = {ort, von0[ort]-von0[parent0[ort]]};
        ort = parent0[ort];
    }
    ort = 0;
    while(parentn[ort]!=-1){
        in_shortest_path[parentn[ort]] = {ort, vonn[ort]-vonn[parentn[ort]]};
        ort = parentn[ort];
    }
    /*if(von0[v-1]==1e17 && vonn[0]==1e17){
        cout << -1;
        exit(0);
    }*/
    int res = von0[v-1]+vonn[0];//keine Kante gedreht
    for(int i=0; i<e; i++){
        auto [start, ende, kosten, umdrehkosten] = edges[i];
        pair<int,int> temp = {ende, kosten};
        if(in_shortest_path[start] == temp){
            adj[start].erase(make_tuple(ende, kosten, umdrehkosten));
            adj[ende].insert(make_tuple(start, kosten, umdrehkosten));
            vector<long long> dist(v, 1e17), p(v, -1), dist2(v, 1e17);
            dijkstra(adj, dist, 0, p);
            dijkstra(adj, dist2, v-1, p);
            if(dist[v-1]<1e17 && dist2[0]<1e17) res = min(res, dist[v-1]+dist2[0]+umdrehkosten);
            adj[start].insert(make_tuple(ende, kosten, umdrehkosten));
            adj[ende].erase(make_tuple(start, kosten, umdrehkosten));
        }else{
            res = min(res, min(vonn[0], vonn[ende]+kosten+von0_r[start]) + min(von0[v-1], von0[ende]+kosten+vonn_r[start]) + umdrehkosten);
        }
    }
    if(res<1e17) cout << res;
    else cout << -1;
    return 0;
}

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