oj.uz

Submission #758682

# Submission time Handle Problem Language Result Execution time Memory
758682 2023-06-15T06:00:48 Z xyzxyz Olympic Bus (JOI20_ho_t4) C++17
32 / 100
 632 ms 9580 KB 
#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];
    }
    int res = min((long long)1e17, (long long)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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 556 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Incorrect 16 ms 552 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9152 KB Output is correct
2 Correct 66 ms 9164 KB Output is correct
3 Correct 65 ms 9292 KB Output is correct
4 Correct 3 ms 624 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 34 ms 9300 KB Output is correct
10 Correct 35 ms 9344 KB Output is correct
11 Correct 67 ms 9284 KB Output is correct
12 Correct 56 ms 9260 KB Output is correct
13 Correct 56 ms 9312 KB Output is correct
14 Correct 65 ms 9580 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 312 ms 7076 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 632 ms 9096 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 289 ms 9072 KB Output is correct
9 Correct 298 ms 9260 KB Output is correct
10 Correct 438 ms 9036 KB Output is correct
11 Correct 375 ms 9164 KB Output is correct
12 Correct 474 ms 8996 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 ms 320 KB Output is correct
19 Correct 407 ms 9060 KB Output is correct
20 Correct 386 ms 9036 KB Output is correct
21 Correct 409 ms 9036 KB Output is correct
22 Correct 411 ms 9036 KB Output is correct

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 556 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Incorrect 16 ms 552 KB Output isn't correct
11 Halted 0 ms 0 KB -