Submission #310310

#	Time	Username	Problem	Language	Result	Execution time	Memory
310310		nicolaalexandra	Cities (BOI16_cities)	C++14	100 / 100	3552 ms	47460 KiB

cities

#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 (stderr)

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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26