Submission #866631

#	Time	Username	Problem	Language	Result	Execution time	Memory
866631		salmon	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	43 ms	5384 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];
bool visited[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;

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

            pair<int,int> small = make_pair(0,1);

            tempd[1] = 0;

            while(small.second != -1){
                visited[small.second] = true;

                if(edge[i][1] == small.second){
                    tempd[edge[i][0]] = min(tempd[edge[i][0]], tempd[small.second]  + edge[i][2]);
                }
                for(int j : adjlst[small.second]){
                    if(j == i) continue;
                    tempd[edge[j][1]] = min(tempd[edge[j][1]], tempd[small.second]  + edge[j][2]);
                }

                small = make_pair(-1,-1);
                for(int i = 1; i <= N; i++){
                    if(!visited[i]) small = min(small, make_pair(tempd[i],i));
                }
            }


            temp = tempd[N];
        }
        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;
                visited[i] = false;
            }

            pair<int,int> small = make_pair(0,N);

            tempd[N] = 0;

            while(small.second != -1){
                visited[small.second] = true;

                if(edge[i][1] == small.second){
                    tempd[edge[i][0]] = min(tempd[edge[i][0]], tempd[small.second]  + edge[i][2]);
                }
                for(int j : adjlst[small.second]){
                    if(j == i) continue;
                    tempd[edge[j][1]] = min(tempd[edge[j][1]], tempd[small.second]  + edge[j][2]);
                }

                small = make_pair(-1,-1);
                for(int i = 1; i <= N; i++){
                    if(!visited[i]) small = min(small, make_pair(tempd[i],i));
                }
            }


            temp = tempd[1];
        }
        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:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
ho_t4.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
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",&u);
      |         ~~~~~^~~~~~~~~~
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",&v);
      |         ~~~~~^~~~~~~~~~
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",&c);
      |         ~~~~~^~~~~~~~~~
ho_t4.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf(" %d",&d);
      |         ~~~~~^~~~~~~~~~

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