oj.uz

Submission #815685

# Submission time Handle Problem Language Result Execution time Memory
815685 2023-08-08T18:29:00 Z anton Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 3476 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);
    }

    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;
    }

    find_d();
    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;
            int cost = edges[i].c + edges[i].d;
            res = min(res, min(find_len(0, v-1) + find_len(v-1, from) +edges[i].c+ find_len(to, 0),  find_len(v-1, 0) + find_len(0, from) +edges[i].c+ find_len(to, v-1))+  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;
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:161:17: warning: unused variable 'cost' [-Wunused-variable]
  161 |             int cost = edges[i].c + edges[i].d;
      |                 ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 672 KB Output is correct
2 Correct 9 ms 596 KB Output is correct
3 Correct 104 ms 676 KB Output is correct
4 Correct 114 ms 680 KB Output is correct
5 Correct 27 ms 428 KB Output is correct
6 Correct 9 ms 596 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 6 ms 340 KB Output is correct
10 Correct 165 ms 676 KB Output is correct
11 Correct 147 ms 596 KB Output is correct
12 Correct 153 ms 676 KB Output is correct
13 Incorrect 54 ms 692 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 3476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 676 KB Output is correct
2 Correct 10 ms 640 KB Output is correct
3 Execution timed out 1089 ms 2672 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 672 KB Output is correct
2 Correct 9 ms 596 KB Output is correct
3 Correct 104 ms 676 KB Output is correct
4 Correct 114 ms 680 KB Output is correct
5 Correct 27 ms 428 KB Output is correct
6 Correct 9 ms 596 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 6 ms 340 KB Output is correct
10 Correct 165 ms 676 KB Output is correct
11 Correct 147 ms 596 KB Output is correct
12 Correct 153 ms 676 KB Output is correct
13 Incorrect 54 ms 692 KB Output isn't correct
14 Halted 0 ms 0 KB -