Submission #864886

#	Time	Username	Problem	Language	Result	Execution time	Memory
864886		salmon	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	47 ms	4312 KiB

ho_t4

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

int f1d[210],b1d[210];
int fnd[210],bnd[210];
vector<int> adjlst[210];
vector<int> badjlst[210];
vector<int> tempadjlst[210];
vector<int> tempbadjlst[210];
int parent[210];
int p[210];
int N,M;
vector<int> edge[50100];
int u, v, c, d;
int inf = 2e9;
vector<int> fpath;
vector<int> bpath;
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;
    }

    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] = edge[ii.second][0];

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

    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;

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

    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++){
        small = min(small, min((long long int)f1d[N], f1d[edge[i][1]] + (long long int)bnd[edge[i][0]] ) + (long long int)min((long long int)fnd[1], fnd[edge[i][1]] + (long long int)b1d[edge[i][0]] ) + 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