oj.uz

답안 #537823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537823 2022-03-15T15:44:09 Z __Variatto Cities (BOI16_cities) C++17
0 / 100
 1002 ms 39612 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10, K=1<<5;
const ll MAXV=1e8+10;/////////////
int n, k, m, spe[10];
ll dp[K][MAX];
bool odw[MAX];
vector<pair<int,ll>>g[MAX];
priority_queue<pair<ll,int>>kol;
void dijkstra(int maska){
    while(kol.size()){
        auto v=kol.top();
        kol.pop();
        v.fi*=-1;
        if(odw[v.se]) continue;
        odw[v.se]=true;
        for(auto s:g[v.se])
            if(dp[maska][s.fi]>dp[maska][v.se]+s.se)
                dp[maska][s.fi]=dp[maska][v.se]+s.se, kol.push({-dp[maska][s.fi], s.fi});
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>k>>m;
    for(int i=1; i<=k; i++)
        cin>>spe[i-1];
    for(int i=1; i<=m; i++){
        int a, b, c;
        cin>>a>>b>>c;
        g[a].pb({b, c}), g[b].pb({a, c});
    }
    for(int i=1; i<K; i++)
        for(int j=1; j<=n; j++)
            dp[i][j]=MAXV;
    for(int i=1; i<K; i++){
        int x=i;
        vector<int>pos;
        int l=0;
        while(x){
            if(x%2) pos.pb(l);
            x/=2, l++;
        }
        if(pos.size()==1)
            dp[i][spe[pos[0]]]=0;
        for(int j=1; j<=n; j++)
            odw[j]=false;
        for(int j=1; j<=n; j++){
            for(int j1=1; j1<(1<<(int)pos.size()); j1++){
                x=j1, l=0;
                int aktMask=0;
                while(x){
                    if(x%2==1) aktMask+=(1<<(pos[l]));
                    x/=2, l++;
                }
                //cout<<i<<" "<<aktMask<<"\n";
                dp[i][j]=min(dp[i][j], dp[aktMask][j]+dp[i^aktMask][j]);
            }
            kol.push({-dp[i][j], j});
        }
        dijkstra(i);
    }
    ll mini=MAXV;
    for(int i=1; i<=n; i++)
        mini=min(mini, dp[(1<<k)-1][i]);
    cout<<mini<<"\n";
}

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Incorrect 2 ms 2772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 935 ms 39600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 3204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1002 ms 39612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 893 ms 39496 KB Output isn't correct
2 Halted 0 ms 0 KB -