제출 #1126687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126687		TVSown	Cities (BOI16_cities)	C++20	22 / 100	99 ms	26180 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 = 1e6 + 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;
    }
}

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);
    if(n <= 20) sub1::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();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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