oj.uz

Submission #96252

# Submission time Handle Problem Language Result Execution time Memory
96252 2019-02-07T13:02:46 Z easrui Cities (BOI16_cities) C++14
100 / 100
 2264 ms 42396 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int MN = 1e5+5;
long long N,K,M,A,B,d,sz,Im[5],cur,tmp,cost,ans,D[32][MN];
vector<pii> G[MN];
priority_queue<pii> Q;
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N >> K >> M;
    for(int i=0; i<K; i++) cin >> Im[i];
    for(int i=0; i<M; i++){
        cin >> A >> B >> d;
        G[A].push_back(pii(B,d));
        G[B].push_back(pii(A,d));
    }
    sz = 1<<K;
    for(int i=0; i<sz; i++)
        for(int j=1; j<=N; j++) D[i][j] = 1e18;
    for(int j=0; j<K; j++) D[(1<<j)][Im[j]] = 0;
    for(int i=1; i<sz; i++){
        for(int j=1; j<=N; j++){
            tmp = 1e18;
            for(int p=1; p<sz/2; p++){
                if((p&i)!=p) continue;
                tmp = min(tmp,D[i-p][j] + D[p][j]);
            }
            D[i][j] = min(D[i][j],tmp);
            Q.emplace(-D[i][j],j);
        }
        while(!Q.empty()){
            cur = Q.top().vb;
            cost = -Q.top().va;
            Q.pop();
            if(cost>D[i][cur]) continue;
            for(pii x : G[cur]){
                if(D[i][x.va] > cost + x.vb){
                    D[i][x.va] = cost + x.vb;
                    Q.emplace(-D[i][x.va],x.va);
                }
            }
        }
    }
    ans = 1e18;
    for(int j=1; j<=N; j++) ans = min(ans,D[sz-1][j]);
    cout << ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 3 ms 2808 KB Output is correct
5 Correct 4 ms 2936 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 23628 KB Output is correct
2 Correct 659 ms 22792 KB Output is correct
3 Correct 444 ms 16488 KB Output is correct
4 Correct 83 ms 11744 KB Output is correct
5 Correct 375 ms 20444 KB Output is correct
6 Correct 77 ms 11640 KB Output is correct
7 Correct 6 ms 2936 KB Output is correct
8 Correct 5 ms 2936 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3064 KB Output is correct
2 Correct 9 ms 3064 KB Output is correct
3 Correct 7 ms 2936 KB Output is correct
4 Correct 7 ms 3196 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1221 ms 29780 KB Output is correct
2 Correct 1158 ms 28892 KB Output is correct
3 Correct 782 ms 22760 KB Output is correct
4 Correct 641 ms 21612 KB Output is correct
5 Correct 194 ms 14136 KB Output is correct
6 Correct 84 ms 14072 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2176 ms 42396 KB Output is correct
2 Correct 2264 ms 42316 KB Output is correct
3 Correct 2204 ms 41440 KB Output is correct
4 Correct 1681 ms 35180 KB Output is correct
5 Correct 1203 ms 27884 KB Output is correct
6 Correct 305 ms 15504 KB Output is correct
7 Correct 92 ms 14076 KB Output is correct