Submission #1126970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126970		TVSown	Cities (BOI16_cities)	C++20	0 / 100	199 ms	49536 KiB

cities

///*** Sown_Vipro ***///
/// ->NHI QUOC GIA<- ///

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define all(s) s.begin(), s.end()
#define szz(s) int(s.size())
const string NAME = "sown";
const int N = 3e5 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
void maxi(int &x, int y){ if(x < y) x = y; }
void maxill(long long &x, long long y){ if(x < y) x = y; }
void mini(int &x, int y){ if(x > y) x = y; };
void minill(long long &x, long long y){ if(x > y) x = y; };
void add(int &x, int y){ x += y; x += MOD * (x < 0); x -= MOD * (x >= MOD); };
int n, k, m;
int spe[N];
struct edge{
    int u, v, w;
} e[N];

bool cmp(edge a, edge b){
    return a.w < b.w;
}

namespace sub1{
    int p[N];

    int Find(int u){
        if(u == p[u]) return u;
        return p[u] = Find(p[u]);
    }

    int Union(int u, int v){
        u = Find(u);
        v = Find(v);
        if(u == v) return 0;

        p[v] = u;
        return 1;
    }

    int vst[N];
    vector<int> adj[N];
    void dfs(int u){
        vst[u] = 1;
        for(int v : adj[u]){
            if(vst[v]) continue;
            dfs(v);
        }
    }

    void solve(){
        long long res = 1e18;

        FOR(mask, 1, (1 << n) - 1){
            int check = 1;
            FOR(i, 1, k){
                if(!(mask & (1 << spe[i] - 1))) check = 0;
            }
            if(!check) continue;


//            FOR(u, 1, n){
//                if(mask & (1 << u - 1)) cout << u << " ";
//            }
//            cout << "\n";
//            cout << mask << "\n";
            FOR(u, 1, n) p[u] = u;
            long long sum = 0;
            FOR(i, 1, m){
                int u = e[i].u, v = e[i].v, w = e[i].w;
                if((mask & (1 << u - 1)) && (mask & (1 << v - 1))){
                    if(Union(u, v)){
//                        cout << u << " " << v << " " << w << "\n";
                        sum += w;
                        adj[u].pb(v);
                        adj[v].pb(u);
                    }
                }
            }
            dfs(spe[1]);
            FOR(i, 1, k) if(!vst[spe[i]]) check = 0;
//            cout << sum << "\n";
            if(check) minill(res, sum);
            FOR(u, 1, n){
                vst[u] = 0;
                adj[u].clear();
            }
        }
        cout << res;
    }
}

namespace sub2{
    vector<vector<long long> > d(10, vector<long long> (N));
    vector<pi> adj[N];

    void dt(int S, vector<long long> &d){
        FOR(u, 1, n) d[u] = 1e18;
        priority_queue<pair<long long, int> > pq;
        pq.push({0, S});
        d[S] = 0;
        while(szz(pq)){
            int u = pq.top().S;
            long long du = -pq.top().F;
            pq.pop();

            if(du != d[u]) continue;
            for(auto [v, w] : adj[u]){
                if(du + w < d[v]){
                    d[v] = du + w;
                    pq.push({-d[v], v});
                }
            }
        }
    }

    void solve(){
        FOR(i, 1, m){
            adj[e[i].u].pb({e[i].v, e[i].w});
            adj[e[i].v].pb({e[i].u, e[i].w});
        }

        dt(spe[1], d[1]);
        dt(spe[2], d[2]);
        dt(spe[3], d[3]);

        long long res = 1e18;
        FOR(u, 1, n){
//            cout << u << " " << d[1][u] << " " << d[2][u] << " " << d[3][u] << "\n";
            minill(res, d[1][u] + d[2][u] + d[3][u]);
        }
        cout << res;
    }
}

void solve(){
    cin >> n >> k >> m;
    FOR(i, 1, k){
        cin >> spe[i];
    }
    FOR(i, 1, m){
        int u, v, w; cin >> u >> v >> w;
        e[i] = {u, v, w};
    }
    sort(e + 1, e + 1 + m, cmp);
    sub2::solve();
//    if(n <= 20) sub1::solve();
//    else if(k == 3) sub2::solve();
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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