oj.uz

Submission #758238

# Submission time Handle Problem Language Result Execution time Memory
758238 2023-06-14T10:08:22 Z xyzxyz Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 8196 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];
    }
    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+umdrehkosten+von0_r[start]) + min(von0[v-1], von0[ende]+kosten+umdrehkosten+vonn_r[start]));
        }
    }
    if(res<1e17) cout << res;
    else cout << -1;
    return 0;
}

Compilation message

ho_t4.cpp: In function 'void dijkstra(std::vector<std::set<std::tuple<long long int, long long int, long long int> > >&, std::vector<long long int>&, long long int, std::vector<long long int>&)':
ho_t4.cpp:16:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |                 auto [ziel, kosten, umdrehkosten] = next;
      |                      ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |         auto [start, ende, kosten, umdrehkosten] = edges[i];
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 340 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 17 ms 532 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 8180 KB Output is correct
2 Correct 155 ms 8148 KB Output is correct
3 Correct 131 ms 8184 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 40 ms 8148 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 776 ms 6464 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Execution timed out 1075 ms 8196 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 340 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 17 ms 532 KB Output isn't correct
11 Halted 0 ms 0 KB -