Submission #1291118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291118		herominhsteve	Cities (BOI16_cities)	C++20	100 / 100	1026 ms	43200 KiB

cities

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 1e5 + 5;
const long long INF = 1e16 + 15092007;

struct Edges{
    int v;
    long long w;
    Edges(): v(0),w(0) {}
    Edges(int V,long long W):v(V),w(W) {}
    bool operator < (const Edges &other) const{
        return w>other.w;
    }
};

int n,m,K;
vector<Edges> graph[MAXN];
vector<int> crucial;

void init(){
    cin>>n>>K>>m;
    crucial.resize(K);
    for (int &x : crucial) cin>>x,x--;
    for (int i=0;i<m;i++){
        int u,v;
        long long w;
        cin>>u>>v>>w;
        u--; v--;
        graph[u].emplace_back(v,w);
        graph[v].emplace_back(u,w);
    }
}

void sol(){
    int MAXMASK = 1 << K;
    vector<vector<long long>> distancia(MAXMASK,vector<long long>(n,INF));
    for (int i=0;i<K;i++){
        distancia[1<<i][crucial[i]] = 0;
    }
    priority_queue<Edges> pq;
    for (int mask = 1; mask < MAXMASK; mask++){
        for (int prevMask=0;prevMask < mask; prevMask++) if ((prevMask | mask) == mask){
            int othermask = mask ^ prevMask;
            if (othermask > prevMask) continue;
            for (int city = 0; city < n; city++){
                minimize(distancia[mask][city], distancia[prevMask][city] + distancia[othermask][city]);
            }
        }

        for (int u = 0; u < n; u++){
            if (distancia[mask][u] < INF){
                pq.emplace(u, distancia[mask][u]);
            }
        }

        while (!pq.empty()){
            int u = pq.top().v;
            long long dis = pq.top().w;
            pq.pop();
            if (dis > distancia[mask][u]) continue;
            for (const Edges &x : graph[u]){
                int v = x.v;
                long long w = x.w;
                if (minimize(distancia[mask][v], distancia[mask][u] + w)){
                    pq.emplace(v, distancia[mask][v]);
                }
            }
        }
    }
    long long res = INF;
    for (int city = 0; city < n; city++){
        minimize(res, distancia[MAXMASK - 1][city]);
    }
    cout<<res;
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

cities.cpp: In function 'void setup()':
cities.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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