Submission #290681

#	Time	Username	Problem	Language	Result	Execution time	Memory
290681		giorgikob	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	151 ms	4088 KiB

ho_t4

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const ll MX = 1e15;

int n,m;
ll dist[205][205], dist1[205][205], dist2[205][205];
ll ind[205][205];
int fix[50005], fix1[50005];
int X[50005],Y[50005];
ll c[50005], d[50005];
ll answer;

void rec(int x,int y,vector<int>&v){
        ll k = ind[x][y];
        if(k == MX){
                return ;
        }
        if(k < 0){
                v.pb(-k);
                fix[-k] = 1;
                fix1[-k] = 1;
                return ;
        }
        rec(x,k,v);
        rec(k,y,v);
}

int main(){

        cin >> n >> m;

        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                        dist[i][j] = MX;
                        dist1[i][j] = MX;
                        dist2[i][j] = MX;
                        ind[i][j] = MX;
                }
        }

        for(int i = 1; i <= n; i++) {
                dist[i][i] = 0;
                dist1[i][i] = 0;
                dist2[i][i] = 0;
        }

        for(int i = 1; i <= m; i++){
                int x,y;
                cin >> x >> y >> c[i] >> d[i];
                dist[x][y] = min(dist[x][y], c[i]);
                ind[x][y] = -i;
                X[i] = x; Y[i] = y;
        }

        //disjkstra(1);


        for(int k = 1; k <= n; k++){
                for(int i = 1; i <= n; i++){
                        for(int j = 1; j <= n; j++){
                                ll new_dist = dist[i][k] + dist[k][j];
                                if(dist[i][j] > new_dist){
                                        dist[i][j] = new_dist;
                                        ind[i][j] = k;
                                }
                        }
                }
        }
        //cout << dist[1][n] << " " << dist[n][1] << endl;
        vector<int>path1, path2;

        rec(1,n,path1);

        for(int i = 1; i <= m; i++){
                if(fix[i]){
                        fix[i] = 0;
                        continue;
                }
                int x = X[i], y = Y[i];
                dist1[x][y] = min(dist1[x][y], c[i]);
        }
        //cout << "ok" << endl;
        rec(n,1,path2);

        for(int i = 1; i <= m; i++){
                if(fix[i]){
                        fix[i] = 0;
                        continue;
                }
                int x = X[i], y = Y[i];
                dist2[x][y] = min(dist2[x][y], c[i]);
        }
        //cout << "ok" << endl;
        //for(auto x : path1) cout << x << " "; cout << endl;
        //for(auto x : path2) cout << x << " "; cout << endl;

        for(int k = 1; k <= n; k++){
                for(int i = 1; i <= n; i++){
                        for(int j = 1; j <= n; j++){
                                ll new_dist = dist1[i][k] + dist1[k][j];
                                if(dist1[i][j] > new_dist){
                                        dist1[i][j] = new_dist;
                                }
                                new_dist = dist2[i][k] + dist2[k][j];
                                if(dist2[i][j] > new_dist){
                                        dist2[i][j] = new_dist;
                                }
                        }
                }
        }

        answer = dist[1][n] + dist[n][1];

        for(int k = 0; k < (int)path1.size(); k++){
                for(int i = 0; i <= k; i++){
                        for(int j = k; j < (int)path1.size(); j++){
                                int ind1 = path1[i];
                                int ind2 = path1[j];
                                int x = X[ind1], y = Y[ind2];
                                ll new_dist = dist[1][x] + dist1[x][y] + dist[y][n] + d[path1[k]] + dist[n][1];
                                //cout << x << " " << y << " " << new_dist << endl;
                                answer = min(answer, new_dist);
                        }
                }
        }

        for(int k = 0; k < (int)path2.size(); k++){
                for(int i = 0; i <= k; i++){
                        for(int j = k; j < (int)path2.size(); j++){
                                int ind1 = path2[i];
                                int ind2 = path2[j];
                                int x = X[ind1], y = Y[ind2];
                                ll new_dist = dist[n][x] + dist1[x][y] + dist[y][1] + d[path2[k]] + dist[1][n];
                                answer = min(answer, new_dist);
                        }
                }
        }

        for(int i = 1; i <= m; i++){
                if(fix1[i])continue;
                int x = X[i];
                int y = Y[i];
                ll new_dist = d[i] + min(dist[1][n], dist[1][y] + c[i] + dist[x][n]) + min(dist[n][1], dist[n][y] + c[i] + dist[x][1]);
                //cout << x << " " << y << " " << new_dist << endl;
                answer = min(answer, new_dist);
        }


        if(answer >= MX){
                answer = -1;
        }

        cout << answer << endl;

}

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