Submission #310308

#	Time	Username	Problem	Language	Result	Execution time	Memory
310308		nicolaalexandra	Cities (BOI16_cities)	C++14	74 / 100	6092 ms	170584 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,pair<int,int> >, vector<pair<long long,pair<int,int> > >, greater<pair<long long,pair<int,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;
        H.push(make_pair(0,make_pair(v[i],(1<<(i-1)))));
    }

    long long sol = INF;
    while (!H.empty()){
        int nod = H.top().second.first;
        int stare = H.top().second.second;
        long long cst = H.top().first;
        if (stare == (1<<k)-1)
            sol = min (sol,cst);
        H.pop();
        if (cst != dp[nod][stare])
            continue;
        for (auto it : L[nod]){
            int vecin = it.first, cost = it.second;

            /// trb sa combin starea curenta cu toate starile care ar putea di in vecin
            int val = ((1<<k)-1) ^ stare;
            for (int new_stare=val;new_stare>=0;new_stare=(new_stare-1)&val){
                if (dp[nod][stare] + dp[vecin][new_stare] + cost < dp[vecin][stare|new_stare]){
                    dp[vecin][stare|new_stare] = dp[nod][stare] + dp[vecin][new_stare] + cost;
                    H.push(make_pair(dp[vecin][stare|new_stare],make_pair(vecin,stare|new_stare)));
                }
                if (!new_stare)
                    break;
            }}}

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

    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
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: 0 / 26