제출 #290811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290811		giorgikob	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	55 ms	3064 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], fix2[50005];
int X[50005],Y[50005];
ll c[50005], d[50005];
ll answer;
ll B[50005];

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;
                return ;
        }
        rec(x,k,v);
        rec(k,y,v);
}

int main(){
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        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;
                                }
                        }
                }
        }
        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++){
                fix1[path1[k]] = 1;
                int ind = path1[k];
                int xx = X[ind];
                int yy = Y[ind];
                ll res = MX;
                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];
                                res = min(res, dist[1][x] + dist1[x][y] + dist[y][n]);// + d[path1[k]];
                        }
                }
                B[ind] = res;
                if(!fix2[ind]) B[ind] += min(dist[n][yy] + c[ind] + dist[xx][1],dist[n][1]) + d[ind];
        }

        for(int k = 0; k < (int)path2.size(); k++){
                fix2[path2[k]] = 1;
                int ind = path2[k];
                int xx = X[ind];
                int yy = Y[ind];
                ll res = 0;
                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];
                                res = min(res, dist[n][x] + dist2[x][y] + dist[y][1]);
                        }
                }
                B[ind] += res;
                if(!fix1[ind]){
                        B[ind] += min(dist[1][yy] + c[ind] + dist[xx][n], dist[1][n]) + d[ind];
                } else {
                        B[ind] += d[ind];
                }
        }

        for(int i = 1; i <= m; i++){
                if(B[i] > 0)
                answer = min(B[i], answer);
        }

        for(int i = 1; i <= m; i++){
                if(fix1[i] || fix2[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;
        }
        if(answer < -1) {
                cout << 1/0 << endl;
        }

        cout << answer << endl;

}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:177:26: warning: division by zero [-Wdiv-by-zero]
  177 |                 cout << 1/0 << endl;
      |                         ~^~

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