oj.uz

Submission #815690

# Submission time Handle Problem Language Result Execution time Memory
815690 2023-08-08T18:41:10 Z anton Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 54 ms 3532 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>


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

const int MAX_E = 5*1e4;
const int MAX_V = 200;
const int INF = 1e15;
int v, e;
Edge edges[MAX_E];
vector<pii> adj[MAX_V];

int find_len(int begin, int dest){
    vector<int> dist(v, INF);
    vector<pii> prev(v, pii(-1, -1));
    dist[begin] = 0;

    priority_queue<pii> pq;
    pq.push(pii(0, begin));

    while(pq.size()>0){
        auto cur = pq.top();
        pq.pop();

        int u = cur.second;
        int u_dist = -cur.first;

        if(dist[u] == u_dist){
            //cout<<u<<" "<<dist[u]<<endl;
            for(auto next: adj[u]){
                int next_dist = u_dist + edges[next.second].c;
                if(next_dist< dist[next.first]){
                    dist[next.first] = next_dist;
                    pq.push(pii(-next_dist, next.first));
                    prev[next.first].first = u;
                    prev[next.first].second = next.second;
                }
            }
        }
    }
    return dist[dest];
}
vector<int> find_path(int begin, int dest){
    vector<int> dist(v, INF);
    vector<pii> prev(v, pii(-1, -1));
    dist[begin] = 0;

    priority_queue<pii> pq;
    pq.push(pii(0, begin));

    while(pq.size()>0){
        auto cur = pq.top();
        pq.pop();

        int u = cur.second;
        int u_dist = -cur.first;

        if(dist[u] == u_dist){
            //cout<<u<<" "<<dist[u]<<endl;
            for(auto next: adj[u]){
                int next_dist = u_dist + edges[next.second].c;
                if(next_dist< dist[next.first]){
                    dist[next.first] = next_dist;
                    pq.push(pii(-next_dist, next.first));
                    prev[next.first].first = u;
                    prev[next.first].second = next.second;
                }
            }
        }
    }

    if(dist[dest] == INF){
        return vector<int>(0);
    }
    else{
        int cur = dest;
        vector<int> res;
        while(cur!=begin){
            res.push_back(prev[cur].second);
            cur = prev[cur].first;
        }
        return res;
    }
}

int d[MAX_V][MAX_V];
bool is_path[MAX_E];

void find_d(){
    for(int i = 0; i<v; i++){
        for(int j = 0; j<v; j++){
            d[i][j] = INF;
        }
        adj[i].clear();
    }

    for(int i = 0; i<v; i++){
        d[i][i] = 0;
    }
    for(int i = 0; i<e; i++){
            
        d[edges[i].u][edges[i].v] = min(d[edges[i].u][edges[i].v], edges[i].c);
        adj[edges[i].u].push_back(pii(edges[i].v, i));
    }
}

void floyd(){
    for(int mid= 0; mid<v; mid++){
        for(int f= 0; f<v; f++){
            for(int l = 0; l<v; l++){
                d[f][l] = min(d[f][l], d[f][mid] + d[mid][l]);
            }
        }
    }
}

signed main(){
    cin>>v>>e;


    for(int i = 0; i<e; i++){
        cin>>edges[i].u>>edges[i].v>>edges[i].c>>edges[i].d;
        edges[i].u--;
        edges[i].v--;

        //adj[edges[i].u].push_back(pii(edges[i].v, i));
        //d[edges[i].u][edges[i].v] = min(d[edges[i].u][edges[i].v], edges[i].c);
    }

    find_d();

    auto p1 = find_path(0, v-1);
    auto p2 = find_path(v-1, 0);

    if(p1.size()>201||p2.size()>201){
        return 4;
    }
    for(auto e : p1){
        is_path[e] = true;
    }
    for(auto e: p2){
        is_path[e] = true;
    }
    floyd();

    int res = d[0][v-1] + d[v-1][0];

    //cout<<go<<" "<<back<<endl;

    for(int i = 0; i<e; i++){
        //if(!is_path[i]){
            int from = edges[i].v;
            int to = edges[i].u;
            res = min(res, min(d[0][v-1] +  d[v-1][from] +edges[i].c+ d[to][0],  d[0][from] +edges[i].c+ d[to][v-1] + d[v-1][0])+  edges[i].d);
        //}
    }

    for(int i = 0; i<e; i++){
        if(is_path[i]){
            swap(edges[i].u, edges[i].v);
            find_d();
            swap(edges[i].u, edges[i].v);
            res = min(res, find_len(0, v-1) + find_len(v-1, 0) +edges[i].d);
        }
    }

    if(res>=INF){
        cout<<-1<<endl;
        return 0;
    }

    cout<<res<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 596 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 9 ms 696 KB Output is correct
4 Correct 9 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 7 ms 596 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3532 KB Output is correct
2 Correct 52 ms 3528 KB Output is correct
3 Correct 54 ms 3508 KB Output is correct
4 Correct 10 ms 748 KB Output is correct
5 Correct 9 ms 692 KB Output is correct
6 Correct 8 ms 668 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 47 ms 3456 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 696 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 43 ms 2772 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 46 ms 3404 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 596 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 9 ms 696 KB Output is correct
4 Correct 9 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 7 ms 596 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -