Submission #1295125

#TimeUsernameProblemLanguageResultExecution timeMemory
1295125jackofall718Firefighting (NOI20_firefighting)C++20
14 / 100
3094 ms27996 KiB
#include <bits/stdc++.h>
#include <chrono>
#define ll long long int
#define endl '\n'
#define vn vector<ll>
#define vi vector<pair <ll,ll>>

using namespace std;
using namespace std::chrono;
const int MAX_N = 1e9 + 7;
#define pii pair<ll,ll>
const ll INF = 0x3f3f3f3f3f3f3f3f;

#define pb push_back  
#define srt(vp) sort(vp.begin(), vp.end()) 

ll n,k;
vector <vi> adj;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    auto start = high_resolution_clock::now();

    
    cin>>n>>k;
    adj.resize(n+1);
    for (int i=0;i<n-1;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
        
    }
    pair <ll,ll> ans = {MAX_N,0};

    for (int mask=0;mask < (1<<n);mask++){
        ll count = 0;
        vn dist(n+1,INF);
        priority_queue<pair <ll,ll> , vector <pair <ll,ll>>, greater <pair <ll,ll>>>pq;
        for (int i=0;i<n;i++){
            if ((mask >> i) & 1){
                count++;
                pq.push({0,i+1});
                dist[i+1]=0;
            }
        }
        vector <bool>  visited(n+1,false);
        while (!pq.empty()){
            auto [a,b]=pq.top();
            pq.pop();
            if (visited[b])continue;
            visited[b]=true;

            for (auto &x:adj[b]){
                if (dist[x.first]>dist[b]+x.second){
                    dist[x.first]=dist[b]+x.second;
                    pq.push({dist[x.first],x.first});
                }
            }

            
        }
        bool check = true;
        for (int i=1;i<=n;i++){
            if (dist[i]>k)check=false;
        }
        if (check){
            ans = min(ans,{count,mask});
        }

    }
    cout<<ans.first<<endl;
    ll mask = ans.second;
    for (int i=0;i<n;i++){
        if ((mask >> i) & 1)cout<<i+1<<' ';
    }
    cout<<endl;
    
    
    
    


    

    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    //cout << "Time taken by function: " << duration.count() << " microseconds" << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...