Submission #866469

#	Time	Username	Problem	Language	Result	Execution time	Memory
866469		salmon	Olympic Bus (JOI20_ho_t4)	C++14	37 / 100	1085 ms	5396 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;

int f1d[210],b1d[210];
int fnd[210],bnd[210];
int tempd[210];
vector<int> adjlst[210];
vector<int> badjlst[210];
int parent[210];
int p[210];
bool ton[50100],to1[50100];
int N,M;
vector<int> edge[50100];
int u, v, c, d;
int inf = 2e9;
bool is1,isn;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

int main(){
    scanf(" %d",&N);
    scanf(" %d",&M);

    for(int i = 0; i < M; i++){
        scanf(" %d",&u);
        scanf(" %d",&v);
        scanf(" %d",&c);
        scanf(" %d",&d);

        edge[i] = vector<int> {u,v,c,d};

        adjlst[u].push_back(i);
        badjlst[v].push_back(i);
    }

    for(int i = 0; i <= N; i++){
        f1d[i] = inf;
        b1d[i] = inf;
        fnd[i] = inf;
        bnd[i] = inf;
        parent[i] = -1;
    }

    for(int i = 0; i < M; i++){
        ton[1] = false;
        to1[1] = false;
     }

    f1d[1] = 0;

    for(int i : adjlst[1]){
        pq.push(make_pair(edge[i][2],i));
    }

    while(!pq.empty()){
        pair<int,int> ii = pq.top();
        pq.pop();

        int i = edge[ii.second][1];

        if(f1d[i] != inf){
            continue;
        }

        f1d[i] = ii.first;
        parent[i] = ii.second;

        for(int j : adjlst[i]){
            pq.push(make_pair(f1d[i] + edge[j][2],j));
        }
    }

    int t = parent[N];
    while(t != -1){
        ton[t] = true;
        t = parent[edge[t][0]];
    }

    for(int i = 1; i <= N; i++) parent[i] = -1;

    fnd[N] = 0;

    for(int i : adjlst[N]){
        pq.push(make_pair(edge[i][2],i));
    }

    while(!pq.empty()){
        pair<int,int> ii = pq.top();
        pq.pop();

        int i = edge[ii.second][1];

        if(fnd[i] != inf){
            continue;
        }

        fnd[i] = ii.first;
        parent[i] = ii.second;

        for(int j : adjlst[i]){
            pq.push(make_pair(fnd[i] + edge[j][2],j));
        }
    }

    t = parent[1];
    while(t != -1){
        to1[t] = true;
        t = parent[edge[t][0]];
    }

    b1d[1] = 0;

    for(int i : badjlst[1]){
        pq.push(make_pair(edge[i][2],i));
    }

    while(!pq.empty()){
        pair<int,int> ii = pq.top();
        pq.pop();

        int i = edge[ii.second][0];

        if(b1d[i] != inf){
            continue;
        }

        b1d[i] = ii.first;

        for(int j : badjlst[i]){
            pq.push(make_pair(b1d[i] + edge[j][2],j));
        }
    }

    bnd[N] = 0;

    for(int i : badjlst[N]){
        pq.push(make_pair(edge[i][2],i));
    }

    while(!pq.empty()){
        pair<int,int> ii = pq.top();
        pq.pop();

        int i = edge[ii.second][0];

        if(bnd[i] != inf){
            continue;
        }

        bnd[i] = ii.first;

        for(int j : badjlst[i]){
            pq.push(make_pair(bnd[i] + edge[j][2],j));
        }
    }

    long long int small = f1d[N] + (long long int) + fnd[1];
    for(int i = 0; i < M; i++){
        long long int temp = 0;

        int i1 = i;

        if(ton[i]){
            for(int i = 1; i <= N; i++) tempd[i] = inf;

            int l = edge[i1][0];
            edge[i1][0] = edge[i1][1];
            edge[i1][1] = l;

            tempd[1] = 0;
            if(edge[i1][0] == 1){
                pq.push(make_pair(edge[i1][2],i1));
            }
            for(int j : adjlst[1]){
                if(j == i) continue;
                pq.push(make_pair(edge[j][2], j));
            }

            while(!pq.empty()){
                pair<int,int> ii = pq.top();
                pq.pop();

                int i = edge[ii.second][1];

                if(tempd[i] != inf) continue;

                if(edge[i1][0] == i){
                    pq.push(make_pair(edge[i1][2],i1));
                }

                tempd[i] = ii.first;
                for(int j : adjlst[i]){
                    if(j == i1) continue;
                    pq.push(make_pair(tempd[i] + edge[j][2],j));
                }
            }

            temp = tempd[N];

            l = edge[i][0];
            edge[i][0] = edge[i][1];
            edge[i][1] = l;
        }
        else temp = min((long long int)f1d[N], f1d[edge[i][1]] + (long long int)bnd[edge[i][0]] + edge[i][2]);

        if(to1[i]){
            for(int i = 1; i <= N; i++) tempd[i] = inf;

            int l = edge[i][0];
            edge[i][0] = edge[i][1];
            edge[i][1] = l;

            tempd[N] = 0;
            if(edge[i1][0] == N){
                pq.push(make_pair(edge[i1][2],i1));
            }
            for(int j : adjlst[N]){
                if(j == i) continue;
                pq.push(make_pair(edge[j][2], j));
            }

            while(!pq.empty()){
                pair<int,int> ii = pq.top();
                pq.pop();

                int i = edge[ii.second][1];

                if(tempd[i] != inf) continue;

                if(edge[i1][0] == i){
                    pq.push(make_pair(edge[i1][2],i1));
                }

                tempd[i] = ii.first;
                for(int j : adjlst[i]){
                    if(j == i1) continue;
                    pq.push(make_pair(tempd[i] + edge[j][2],j));
                }
            }

            temp += tempd[1];

            l = edge[i][0];
            edge[i][0] = edge[i][1];
            edge[i][1] = l;
        }
        else temp += min((long long int)fnd[1], fnd[edge[i][1]] + (long long int)b1d[edge[i][0]] + edge[i][2]);

        small = min(small, temp + edge[i][3]);
    }
    if(small >= inf){
        printf("-1");
    }
    else{
        printf("%lld",small);
    }
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
ho_t4.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
ho_t4.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
ho_t4.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf(" %d",&v);
      |         ~~~~~^~~~~~~~~~
ho_t4.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf(" %d",&c);
      |         ~~~~~^~~~~~~~~~
ho_t4.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf(" %d",&d);
      |         ~~~~~^~~~~~~~~~

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