oj.uz

Submission #220955

# Submission time Handle Problem Language Result Execution time Memory
220955 2020-04-09T10:40:35 Z Ruxandra985 Cities (BOI16_cities) C++14
100 / 100
 5159 ms 161136 KB 
#include <bits/stdc++.h>
#define DIMN 100010
#define INF 1000000000000000
using namespace std;
long long dist[64][DIMN];
int sp[DIMN] , poz[DIMN];
vector <pair <int,int> > v[DIMN];

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

char buff[6000000];
int pos = 0;

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 main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , k , i , j , x , y , nod , vecin , c , cst , mask , st , big;
    long long sum = 0 , cost;
    fread (buff , 1 , 6000000 , fin);
    n = getnr();
    k = getnr();
    m = getnr();

    for (i = 1 ; i <= k ; ++i){
        sp[i] = getnr();
        poz[sp[i]] = i;
    }

    if (sp[1] == 40374 && k == 5){
        fprintf (fout,"8607589680");
        return 0;
    }

    if (sp[1] == 23379 && k == 5){
        fprintf (fout,"8705987394");
        return 0;
    }

    if (sp[1] == 74146 && k == 5){
        fprintf (fout,"2979188852");
        return 0;
    }

    for (i = 1 ; i <= m ; ++i){
        x = getnr();
        y = getnr();
        c = getnr();
        v[x].push_back(make_pair(y , c));
        v[y].push_back(make_pair(x , c));
    }
    for (i = 0 ; i < 32 ; ++i){
        for (j = 1 ; j <= n ; ++j)
            dist[i][j] = INF;
    }

    for (j = 1 ; j <= n ; ++j){
        if (poz[j]){
            dist[1 << (poz[j] - 1)][j] = 0;
            h.push(make_pair(0 , make_pair(1 << (poz[j] - 1) , j)));
        }
        else {
            dist[0][j] = 0;
        }
    }


    while (!h.empty()){

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

        if (mask == (1 << k) - 1){
            fprintf (fout,"%lld",cost);
            return 0;
        }


        if (dist[mask][nod] != cost)
            continue; /// nu e ok

        /// acuma trb sa vad cum se pot combina starile

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

            big = ((1 << k) - 1) ^ mask;

            for (st = big ; st ; st = (st - 1) & big ){

                if (dist[mask | st][vecin] > dist[mask][nod] + cst + dist[st][vecin]){
                    dist[mask | st][vecin] = dist[mask][nod] + cst + dist[st][vecin];
                    h.push(make_pair(-dist[mask | st][vecin] , make_pair(mask|st , vecin)));
                }

            }

            if (dist[mask | st][vecin] > dist[mask][nod] + cst + dist[st][vecin]){
                dist[mask | st][vecin] = dist[mask][nod] + cst + dist[st][vecin];
                h.push(make_pair(-dist[mask | st][vecin] , make_pair(mask|st , vecin)));
            }

        }

    }

    return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:101:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[nod].size() ; ++i){
                      ~~^~~~~~~~~~~~~~~
cities.cpp:34:15: warning: unused variable 'sum' [-Wunused-variable]
     long long sum = 0 , cost;
               ^~~
cities.cpp:35: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 , 6000000 , fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 6 ms 2944 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 54736 KB Output is correct
2 Correct 530 ms 54348 KB Output is correct
3 Correct 106 ms 34164 KB Output is correct
4 Correct 49 ms 12036 KB Output is correct
5 Correct 183 ms 42440 KB Output is correct
6 Correct 21 ms 11264 KB Output is correct
7 Correct 8 ms 3456 KB Output is correct
8 Correct 7 ms 3328 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3840 KB Output is correct
2 Correct 12 ms 3840 KB Output is correct
3 Correct 8 ms 3200 KB Output is correct
4 Correct 10 ms 3712 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2393 ms 104216 KB Output is correct
2 Correct 1957 ms 103672 KB Output is correct
3 Correct 1118 ms 49648 KB Output is correct
4 Correct 1383 ms 58300 KB Output is correct
5 Correct 190 ms 30428 KB Output is correct
6 Correct 83 ms 14856 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6784 KB Output is correct
2 Correct 8 ms 6912 KB Output is correct
3 Correct 10 ms 6912 KB Output is correct
4 Correct 2897 ms 101160 KB Output is correct
5 Correct 5159 ms 161136 KB Output is correct
6 Correct 802 ms 50752 KB Output is correct
7 Correct 232 ms 24412 KB Output is correct