oj.uz

Submission #758122

# Submission time Handle Problem Language Result Execution time Memory
758122 2023-06-14T07:51:51 Z jasmin Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 38 ms 7224 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int INF=1e17;

struct graph{
    vector<vector<pair<int,int> > >adi;
    vector<int> c;
    vector<int> d;

    graph(int n, int m){
        adi.assign(n, {});
        c.assign(m, 0);
        d.assign(m, 0);
    }

};

void dijkstra(int start, vector<int>& dist, vector<int>& par, int n, graph& g){

    dist.assign(n, INF);
    par.assign(n, -1);
    vector<bool> vis(n, false);
    priority_queue<pair<int,int> > pq;

    dist[start]=0;
    pq.push({-0, start});

    while(!pq.empty()){
        int v=pq.top().second;
        pq.pop();

        if(vis[v]){
            continue;
        }
        vis[v]=true;

        for(auto [u, ind]: g.adi[v]){

            if(dist[v]+g.c[ind] < dist[u]){
                par[u]=ind;
                dist[u] = dist[v] + g.c[ind];
                pq.push({-dist[u], u});
            }

        }
    }

}

vector<int> find_sp(int a, int b, vector<int>& par, vector<pair<int,int> >& edge, int m){
    vector<int> p;
    
    int v=b;
    while(v!=a){

        if(par[v]==-1){
            return {};
        }

        p.push_back(par[v]);
        v=edge[par[v]].first;
    }

    reverse(p.begin(), p.end());
    return p;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    graph g(n, m);
    graph rev(n, m);
    vector<pair<int,int> > edge(m);
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b >> g.c[i] >> g.d[i];
        a--; b--;
        g.adi[a].push_back({b, i});

        rev.c[i]=g.c[i];
        rev.d[i]=g.d[i];
        rev.adi[b].push_back({a, i});

        edge[i]={a, b};
    }

    //distances
    vector<int> par0(n, -1);
    vector<int> to0(n, INF);
    dijkstra(0, to0, par0, n, rev);
    vector<int> from0(n, INF);
    dijkstra(0, from0, par0, n, g);

    vector<int> parn(n, -1);
    vector<int> ton(n, INF);
    dijkstra(n-1, ton, parn, n, rev);
    vector<int> fromn(n, INF);
    dijkstra(n-1, fromn, parn, n, g);


    //paths
    vector<int> path1=find_sp(0, n-1, par0, edge, m);
    vector<int> path2=find_sp(n-1, 0, parn, edge, m);
    
    vector<bool> used(m, false);
    for(auto e: path1){
        used[e]=true;
    }
    for(auto e: path2){
        used[e]=true;
    }


    //possibility 0: turning no edge
    int ans=INF;
    ans = min(ans, from0[n-1] + fromn[0]);

    //possibility 1: edge not on path
    for(int i=0; i<m; i++){
        if(used[i]) continue;

        auto [a, b]=edge[i];

        int d1=from0[b] + g.c[i] + ton[a] + fromn[0];
        int d2=from0[n-1] + fromn[b] + g.c[i] + to0[a];

        int d=min(d1, d2) + g.d[i];
        ans=min(ans, d);
    }

    //possibility 2: edge on path
    vector<int> path;
    for(int i=0; i<m; i++){
        if(used[i]) path.push_back(i);
    }

    for(auto e: path){

        graph neu(n, m);
        for(int i=0; i<m; i++){
            neu.c[i]=g.c[i];
            neu.d[i]=g.d[i];

            auto [a, b]=edge[i];
            if(i==e){
                neu.adi[b].push_back({a, i});
            }
            else{
                neu.adi[a].push_back({b, i});
            }
        }

        int dis=g.d[e];
        vector<int> dist(n, INF);
        vector<int> p(n, -1);
        dijkstra(0, dist, p, n, neu);
        dis += dist[n-1];

        dijkstra(n-1, dist, p, n, neu);
        dis+=dist[0];

        ans=min(ans, dis);
    }

    //output
    if(ans==INF){
        cout << -1 << "\n";
    }
    else{
        cout << ans << "\n";
    }
}

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 468 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 29 ms 504 KB Output is correct
11 Correct 38 ms 492 KB Output is correct
12 Correct 34 ms 468 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7172 KB Output is correct
2 Correct 36 ms 7216 KB Output is correct
3 Correct 35 ms 7224 KB Output is correct
4 Correct 2 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 0 ms 212 KB Output is correct
9 Incorrect 19 ms 5208 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 20 ms 5412 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 28 ms 7016 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 19 ms 5256 KB Output isn't correct
9 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 468 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 29 ms 504 KB Output is correct
11 Correct 38 ms 492 KB Output is correct
12 Correct 34 ms 468 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -