Submission #228729

#	Time	Username	Problem	Language	Result	Execution time	Memory
228729		Ruxandra985	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1094 ms	147200 KiB

ho_t4

#include <bits/stdc++.h>
#define DIMN 210
#define INF 2000000000
using namespace std;
int dp[2][DIMN][50010];


priority_queue <pair < pair <int , int > , pair <int , int > > > h;

vector <pair <int , pair <int , int > > > v[DIMN];

struct idk{

    int x , y , z , c;

} mch[50010];

char buff[5000000];
int pos , n;

int getnr(){
    int nr = 0;

    while ('0' > buff[pos] || buff[pos] > '9')
        pos++;

    while ('0' <= buff[pos] && buff[pos] <= '9'){
        nr = nr * 10 + buff[pos] - '0';
        pos++;
    }

    return nr;

}

int not_worth_it (int stare , int nod , int taken){

    if (stare == 0 && dp[1][n][taken] < dp[stare][nod][taken])
        return 1;
    return 0;

}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int m , x , y , z , c , i , dist , nod , vecin , cost , stare , j , taken , cnt = 0;
    fread (buff , 1 , 5000000 , fin);
    n = getnr();
    m = getnr();
    for (i = 1 ; i <= m ; i++){

        x = getnr();
        y = getnr();
        z = getnr();
        c = getnr();
        v[x].push_back(make_pair(y , make_pair(z , i)));
        mch[i] = {x , y , z , c};
    }

    /// acum faci cele 2 dijkstra uri
    for (i = 1 ; i <= n ; i++)
        for (j = 0 ; j <= m ; j++)
            dp[0][i][j] = dp[1][i][j] = INF;

    for (j = 0 ; j <= m ; j++){
        dp[0][1][j] = mch[j].c;
        h.push(make_pair(make_pair(-mch[j].c , 1) , make_pair(0 , j)));
    }


    while (!h.empty()){

        dist = -h.top().first.first;
        nod = h.top().first.second;
        stare = h.top().second.first;
        taken = h.top().second.second;
        h.pop();

        if (dp[stare][nod][taken] != dist || not_worth_it(stare , nod , taken) || cnt == m)
            continue;

        if (nod == n)
            cnt++;

        if (nod == 1 && stare == 1){
            fprintf (fout,"%d",dist);
            return 0;
        }

        //printf ("%d %d %d %d\n" , nod , stare , taken , dist);


        if (nod == mch[taken].y){ /// caz particular, parcurg muchia intoarsa

            /// parcurgi muchia inversa
            vecin = mch[taken].x;
            cost = mch[taken].z;

            if (vecin == n && stare == 0){

                /// cazul cand se schimba starea

                if (dp[1][vecin][taken] > dist + cost){
                    dp[1][vecin][taken] = dist + cost;
                    h.push(make_pair(  make_pair( -dp[1][vecin][taken] , vecin ) , make_pair( 1 , taken )  ));
                }

            }
            else {
                if (dp[stare][vecin][taken] > dist + cost){
                    dp[stare][vecin][taken] = dist + cost;
                    h.push(make_pair(  make_pair( -dp[stare][vecin][taken] , vecin ) , make_pair( stare , taken )  ));
                }
            }


        }


        for (i = 0 ; i < v[nod].size() ; i++){

            vecin = v[nod][i].first;
            cost = v[nod][i].second.first;

            if (v[nod][i].second.second == taken)
                continue;

            if (vecin == n && stare == 0){

                /// cazul cand se schimba starea

                if (dp[1][vecin][taken] > dist + cost){
                    dp[1][vecin][taken] = dist + cost;
                    h.push(make_pair(  make_pair( -dp[1][vecin][taken] , vecin ) , make_pair( 1 , taken )  ));
                }

            }
            else {
                if (dp[stare][vecin][taken] > dist + cost){
                    dp[stare][vecin][taken] = dist + cost;
                    h.push(make_pair(  make_pair( -dp[stare][vecin][taken] , vecin ) , make_pair( stare , taken )  ));
                }
            }

        }



    }

    fprintf (fout,"-1");

    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:122:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
ho_t4.cpp:49:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread (buff , 1 , 5000000 , fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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