oj.uz

Submission #310310

# Submission time Handle Problem Language Result Execution time Memory
310310 2020-10-06T15:46:51 Z nicolaalexandra Cities (BOI16_cities) C++14
100 / 100
 3552 ms 47460 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define DIMBUFF 6000000
#define INF 2000000000000000000LL
using namespace std;

vector <pair<int,int> > L[DIM];
priority_queue <pair<long long,int> , vector<pair<long long,int> >, greater<pair<long long,int> > > H;
long long dp[DIM][33];
int v[10];
int n,m,k,i,j,x,y,cost,pos;
char buff[DIMBUFF];

int get_nr(){

    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;
    //FILE *fin = fopen ("date.in","r");
    //FILE *fout = fopen ("date.out","w");

    fread (buff,1,DIMBUFF,fin);
    n = get_nr(), k = get_nr(), m = get_nr();

    for (i=1;i<=k;++i)
        v[i] = get_nr();

    for (i=1;i<=m;++i){
        x = get_nr(), y = get_nr(), cost = get_nr();
        L[x].push_back(make_pair(y,cost));
        L[y].push_back(make_pair(x,cost));
    }

    for (i=1;i<=n;++i){
        for (j=0;j<=(1<<k);++j)
            dp[i][j] = INF;

        if (i != v[1] && i != v[2] && i != v[3] && i != v[4] && i != v[5])
            dp[i][0] = 0;
    }

    for (i=1;i<=k;i++)
        dp[v[i]][1<<(i-1)] = 0;


    for (int stare=0;stare<(1<<k);stare++){

        while (!H.empty())
            H.pop();

        /// trb sa combin starea curenta cu toate starile care ar putea fi in fiecare nod
        int val = ((1<<k)-1) ^ stare;
        for (int stare2=stare;stare2>0;stare2 = (stare2-1)&stare)
            for (i=1;i<=n;i++)
                dp[i][stare] = min (dp[i][stare],dp[i][stare2] + dp[i][stare^stare2]);

        for (i=1;i<=n;i++)
            H.push(make_pair(dp[i][stare],i));

        while (!H.empty()){
            int nod = H.top().second;
            long long cst = H.top().first;
            H.pop();
            if (cst != dp[nod][stare])
                continue;

            for (auto it : L[nod]){
                int vecin = it.first, cost = it.second;

                if (dp[nod][stare] + cost < dp[vecin][stare]){
                    dp[vecin][stare] = dp[nod][stare] + cost;
                    H.push(make_pair(dp[vecin][stare],vecin));
                }}}}


    long long sol = INF;
    for (i=1;i<=n;i++)
        sol = min (sol,dp[i][(1<<k)-1]);

    fprintf(fout,"%lld",sol);

    return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:67:13: warning: unused variable 'val' [-Wunused-variable]
   67 |         int val = ((1<<k)-1) ^ stare;
      |             ^~~
cities.cpp:37:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     fread (buff,1,DIMBUFF,fin);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2560 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 43236 KB Output is correct
2 Correct 804 ms 42720 KB Output is correct
3 Correct 531 ms 35952 KB Output is correct
4 Correct 29 ms 11008 KB Output is correct
5 Correct 390 ms 43264 KB Output is correct
6 Correct 24 ms 11000 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 3 ms 3072 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1636 ms 43236 KB Output is correct
2 Correct 1673 ms 42720 KB Output is correct
3 Correct 1127 ms 35948 KB Output is correct
4 Correct 857 ms 27752 KB Output is correct
5 Correct 149 ms 14976 KB Output is correct
6 Correct 37 ms 12664 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3476 ms 43236 KB Output is correct
2 Correct 3521 ms 47460 KB Output is correct
3 Correct 3552 ms 46944 KB Output is correct
4 Correct 2495 ms 38124 KB Output is correct
5 Correct 1809 ms 31852 KB Output is correct
6 Correct 263 ms 18800 KB Output is correct
7 Correct 53 ms 15992 KB Output is correct