Submission #815637

#	Time	Username	Problem	Language	Result	Execution time	Memory
815637		anton	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	144 ms	4724 KiB

ho_t4

#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 = 1e18;
int v, e;
Edge edges[MAX_E];
vector<pii> adj[MAX_V];

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<MAX_V; i++){
        for(int j = 0; j<MAX_V; j++){
            d[i][j] = INF;
        }
    }

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

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()==0){
        cout<<-1<<endl;
        return 0;
    }
    for(auto e: p1){
        is_path[e] = true;
    }
    if(p2.size()==0){
        cout<<-1<<endl;
        return  0;
    }
    for(auto e: p2){
        is_path[e] = true;
    }

    find_d();
    floyd();

    int go = d[0][v-1];
    int back = d[v-1][0];

    int res= go +back;

    //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;
            //cout<<d[v-1][from] + d[to][0]<<" "<<d[0][from] + d[to][v-1]<<endl;
            //cout<<i<<" "<<min(go + d[v-1][from] + d[to][0], back + d[0][from] + d[to][v-1]) + cost<<endl;
            res = min(res, min(go + d[v-1][from] + d[to][0], back + d[0][from] + d[to][v-1]) + cost);
        }
    }

    for(int i = 0; i<e; i++){
        if(is_path[i]){
            int origin = edges[i].u;
            edges[i].u = -1;
            find_d();
            floyd();
            edges[i].u = origin;

            int from = edges[i].v;
            int to = edges[i].u;
            int cost = edges[i].c + edges[i].d;
            //cout<<i<<" "<<min(go + d[v-1][from] + d[to][0], back + d[0][from] + d[to][v-1]) + cost<<endl;
            res = min(res, min(go + d[v-1][from] + d[to][0], back + d[0][from] + d[to][v-1]) + cost);

        }
    }

    cout<<res<<endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63