Submission #310302

#	Time	Username	Problem	Language	Result	Execution time	Memory
310302		nicolaalexandra	Cities (BOI16_cities)	C++14	74 / 100	6078 ms	166404 KiB

cities

#include <bits/stdc++.h>
#define DIM 100010
#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;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>k>>m;

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

    for (i=1;i<=m;i++){
        cin>>x>>y>>cost;
        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)))));
    }

    while (!H.empty()){
        int nod = H.top().second.first;
        int stare = H.top().second.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;

            /// trb sa combin starea curenta cu toate starile care ar putea di in vecin
            for (int new_stare=0;new_stare<(1<<k);new_stare++)
                if (!(stare&new_stare)){
                    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)));
                    }}}}

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

    cout<<sol;

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 26