Submission #866471

#	Time	Username	Problem	Language	Result	Execution time	Memory
866471		salmon	Olympic Bus (JOI20_ho_t4)	C++14	Compilation error	0 ms	0 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;
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:17:65: error: wrong number of template arguments (3, should be at least 1)
   17 | queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
      |                                                                 ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from ho_t4.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:96:11: note: provided for 'template<class _Tp, class _Sequence> class std::queue'
   96 |     class queue
      |           ^~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:51:12: error: request for member 'push' in 'pq', which is of non-class type 'int'
   51 |         pq.push(make_pair(edge[i][2],i));
      |            ^~~~
ho_t4.cpp:54:15: error: request for member 'empty' in 'pq', which is of non-class type 'int'
   54 |     while(!pq.empty()){
      |               ^~~~~
ho_t4.cpp:55:31: error: request for member 'top' in 'pq', which is of non-class type 'int'
   55 |         pair<int,int> ii = pq.top();
      |                               ^~~
ho_t4.cpp:56:12: error: request for member 'pop' in 'pq', which is of non-class type 'int'
   56 |         pq.pop();
      |            ^~~
ho_t4.cpp:68:16: error: request for member 'push' in 'pq', which is of non-class type 'int'
   68 |             pq.push(make_pair(f1d[i] + edge[j][2],j));
      |                ^~~~
ho_t4.cpp:83:12: error: request for member 'push' in 'pq', which is of non-class type 'int'
   83 |         pq.push(make_pair(edge[i][2],i));
      |            ^~~~
ho_t4.cpp:86:15: error: request for member 'empty' in 'pq', which is of non-class type 'int'
   86 |     while(!pq.empty()){
      |               ^~~~~
ho_t4.cpp:87:31: error: request for member 'top' in 'pq', which is of non-class type 'int'
   87 |         pair<int,int> ii = pq.top();
      |                               ^~~
ho_t4.cpp:88:12: error: request for member 'pop' in 'pq', which is of non-class type 'int'
   88 |         pq.pop();
      |            ^~~
ho_t4.cpp:100:16: error: request for member 'push' in 'pq', which is of non-class type 'int'
  100 |             pq.push(make_pair(fnd[i] + edge[j][2],j));
      |                ^~~~
ho_t4.cpp:113:12: error: request for member 'push' in 'pq', which is of non-class type 'int'
  113 |         pq.push(make_pair(edge[i][2],i));
      |            ^~~~
ho_t4.cpp:116:15: error: request for member 'empty' in 'pq', which is of non-class type 'int'
  116 |     while(!pq.empty()){
      |               ^~~~~
ho_t4.cpp:117:31: error: request for member 'top' in 'pq', which is of non-class type 'int'
  117 |         pair<int,int> ii = pq.top();
      |                               ^~~
ho_t4.cpp:118:12: error: request for member 'pop' in 'pq', which is of non-class type 'int'
  118 |         pq.pop();
      |            ^~~
ho_t4.cpp:129:16: error: request for member 'push' in 'pq', which is of non-class type 'int'
  129 |             pq.push(make_pair(b1d[i] + edge[j][2],j));
      |                ^~~~
ho_t4.cpp:136:12: error: request for member 'push' in 'pq', which is of non-class type 'int'
  136 |         pq.push(make_pair(edge[i][2],i));
      |            ^~~~
ho_t4.cpp:139:15: error: request for member 'empty' in 'pq', which is of non-class type 'int'
  139 |     while(!pq.empty()){
      |               ^~~~~
ho_t4.cpp:140:31: error: request for member 'top' in 'pq', which is of non-class type 'int'
  140 |         pair<int,int> ii = pq.top();
      |                               ^~~
ho_t4.cpp:141:12: error: request for member 'pop' in 'pq', which is of non-class type 'int'
  141 |         pq.pop();
      |            ^~~
ho_t4.cpp:152:16: error: request for member 'push' in 'pq', which is of non-class type 'int'
  152 |             pq.push(make_pair(bnd[i] + edge[j][2],j));
      |                ^~~~
ho_t4.cpp:171:20: error: request for member 'push' in 'pq', which is of non-class type 'int'
  171 |                 pq.push(make_pair(edge[i1][2],i1));
      |                    ^~~~
ho_t4.cpp:175:20: error: request for member 'push' in 'pq', which is of non-class type 'int'
  175 |                 pq.push(make_pair(edge[j][2], j));
      |                    ^~~~
ho_t4.cpp:178:23: error: request for member 'empty' in 'pq', which is of non-class type 'int'
  178 |             while(!pq.empty()){
      |                       ^~~~~
ho_t4.cpp:179:39: error: request for member 'top' in 'pq', which is of non-class type 'int'
  179 |                 pair<int,int> ii = pq.top();
      |                                       ^~~
ho_t4.cpp:180:20: error: request for member 'pop' in 'pq', which is of non-class type 'int'
  180 |                 pq.pop();
      |                    ^~~
ho_t4.cpp:187:24: error: request for member 'push' in 'pq', which is of non-class type 'int'
  187 |                     pq.push(make_pair(edge[i1][2],i1));
      |                        ^~~~
ho_t4.cpp:193:24: error: request for member 'push' in 'pq', which is of non-class type 'int'
  193 |                     pq.push(make_pair(tempd[i] + edge[j][2],j));
      |                        ^~~~
ho_t4.cpp:214:20: error: request for member 'push' in 'pq', which is of non-class type 'int'
  214 |                 pq.push(make_pair(edge[i1][2],i1));
      |                    ^~~~
ho_t4.cpp:218:20: error: request for member 'push' in 'pq', which is of non-class type 'int'
  218 |                 pq.push(make_pair(edge[j][2], j));
      |                    ^~~~
ho_t4.cpp:221:23: error: request for member 'empty' in 'pq', which is of non-class type 'int'
  221 |             while(!pq.empty()){
      |                       ^~~~~
ho_t4.cpp:222:39: error: request for member 'top' in 'pq', which is of non-class type 'int'
  222 |                 pair<int,int> ii = pq.top();
      |                                       ^~~
ho_t4.cpp:223:20: error: request for member 'pop' in 'pq', which is of non-class type 'int'
  223 |                 pq.pop();
      |                    ^~~
ho_t4.cpp:230:24: error: request for member 'push' in 'pq', which is of non-class type 'int'
  230 |                     pq.push(make_pair(edge[i1][2],i1));
      |                        ^~~~
ho_t4.cpp:236:24: error: request for member 'push' in 'pq', which is of non-class type 'int'
  236 |                     pq.push(make_pair(tempd[i] + edge[j][2],j));
      |                        ^~~~
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);
      |         ~~~~~^~~~~~~~~~