Submission #233687

#	Time	Username	Problem	Language	Result	Execution time	Memory
233687		Ruxandra985	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	23 ms	2816 KiB

ho_t4

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


priority_queue < 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 dijkstra (int which){
    int i , val , nod , vecin , cost , nr;
    val = 0;
    for (i = 1 ; i <= n ; i++)
        dp[i] = INF;

    dp[1] = 0;
    h.push(make_pair(0 , 1));

    while (!h.empty()){

        nod = h.top().second;
        cost = -h.top().first;
        h.pop();

        if (dp[nod] != cost)
            continue;


        if (nod == mch[which].y){

            cost = dp[nod] + mch[which].z;

            if (dp[mch[which].x] > cost){
                dp[mch[which].x] = cost;
                h.push(make_pair(-cost , mch[which].x));
            }


        }


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

            vecin = v[nod][i].first;
            nr = v[nod][i].second.second;
            if (nr != which){


                cost = dp[nod] + mch[nr].z;
                if (dp[vecin] > cost){
                    dp[vecin] = cost;
                    h.push(make_pair(-cost , vecin));
                }


            }

        }

    }

    val = dp[n];

    /// --------------------------------------------------------------------------


    for (i = 1 ; i <= n ; i++)
        dp[i] = INF;

    dp[n] = 0;
    h.push(make_pair(0 , n));

    while (!h.empty()){

        nod = h.top().second;
        cost = -h.top().first;
        h.pop();

        if (dp[nod] != cost)
            continue;


        if (nod == mch[which].y){

            cost = dp[nod] + mch[which].z;

            if (dp[mch[which].x] > cost){
                dp[mch[which].x] = cost;
                h.push(make_pair(-cost , mch[which].x));
            }


        }


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

            vecin = v[nod][i].first;
            nr = v[nod][i].second.second;
            if (nr != which){


                cost = dp[nod] + mch[nr].z;
                if (dp[vecin] > cost){
                    dp[vecin] = cost;
                    h.push(make_pair(-cost , vecin));
                }


            }

        }

    }

    return val + dp[1];


}


int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int m , x , y , z , c , i , j , k;
    long long sol , val;
    fread (buff , 1 , 5000000 , fin);
    n = getnr();
    m = getnr();

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++){
            dist[i][j] = INF;
        }
        dist[i][i] = 0;
    }


    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};
        dist[x][y] = min(dist[x][y] , z);
    }

    for (k = 1 ; k <= n ; k++){

        for (i = 1 ; i <= n ; i++){

            for (j = 1 ; j <= n ; j++){

                if (i != j && i != k && j != k && dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);

            }
        }

    }

    sol = 1LL * dist[1][n] + dist[n][1];

    /// sol pt cand nu inversez nimic
    /// ce fac daca aleg sa inversez ceva?

    for (i = 1 ; i <= m ; i++){


        /// daca as inversa muchia i as rezolva ceva?

        val = min(1LL * dist[1][n] , 1LL * dist[1][mch[i].y] + dist[mch[i].x][n] + mch[i].z + mch[i].c);
        val += min(1LL * dist[n][1] , 1LL * dist[n][mch[i].y] + mch[i].z + mch[i].c + dist[mch[i].x][1]);

        if (val < sol){
            sol = min(sol , 1LL * dijkstra (i) + mch[i].c);
        }


    }
    if (sol >= INF)
        sol = -1;
    fprintf (fout,"%lld",sol);

    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int dijkstra(int)':
ho_t4.cpp:68:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
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: In function 'int main()':
ho_t4.cpp:154: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