oj.uz

답안 #168759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168759 2019-12-15T23:24:22 Z combi1k1 Cities (BOI16_cities) C++14
100 / 100
 2415 ms 46824 KB 
#pragma GCC optimize "-O3"
#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define X   first
#define Y   second

#define pb  emplace_back

const int   N   = 1e5 + 1;
const ll    inf = 1e18;

typedef pair<ll,int>    ii;

vector<ii>  g[N];
vector<ll>  f[32];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int k;  cin >> k;
    int m;  cin >> m;

    vector<int> imp(k);

    for(int&x : imp)
        cin >> x,
        x--;

    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;   --x;
        int y;  cin >> y;   --y;
        int c;  cin >> c;

        g[x].pb(c,y);
        g[y].pb(c,x);
    }
    for(int i = 0 ; i < 32 ; ++i)
        f[i].assign(n,inf);

    for(int i = 0 ; i < k ; ++i)
        f[1 << i][imp[i]] = 0;

    priority_queue<ii,vector<ii>,greater<ii> >  pq;

    for(int c = 1 ; c < (1 << k) ; ++c) {
        for(int a = c ; a ; a = (a - 1) & c)
        for(int i = 0 ; i < n ; ++i)
            if (f[c][i] > f[a][i] + f[c ^ a][i])
                f[c][i] = f[a][i] + f[c ^ a][i];

        for(int i = 0 ; i < n ; ++i)    if (f[c][i] != inf)
            pq.push(ii(f[c][i],i));

        while (pq.size())   {
            ll du = pq.top().X;
            int u = pq.top().Y;

            pq.pop();

            if (du != f[c][u])
                continue;

            for(ii  e : g[u])   {
                int v = e.Y;
                ll  C = e.X;

                if (f[c][v] > du + C)   {
                    f[c][v] = du + C;
                    pq.push(ii(f[c][v],v));
                }
            }
        }
    }

    ll  ans = inf;

    for(int i = 0 ; i < n ; ++i)
        if (ans > f[(1 << k) - 1][i])
            ans = f[(1 << k) - 1][i];

    cout << ans << endl;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 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 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 628 ms 46748 KB Output is correct
2 Correct 593 ms 45844 KB Output is correct
3 Correct 355 ms 37356 KB Output is correct
4 Correct 96 ms 15352 KB Output is correct
5 Correct 344 ms 46640 KB Output is correct
6 Correct 103 ms 15352 KB Output is correct
7 Correct 8 ms 3192 KB Output is correct
8 Correct 6 ms 3192 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 3064 KB Output is correct
2 Correct 10 ms 3192 KB Output is correct
3 Correct 8 ms 3064 KB Output is correct
4 Correct 8 ms 2936 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1242 ms 46820 KB Output is correct
2 Correct 1157 ms 45912 KB Output is correct
3 Correct 843 ms 37356 KB Output is correct
4 Correct 694 ms 31980 KB Output is correct
5 Correct 210 ms 18660 KB Output is correct
6 Correct 101 ms 17444 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2415 ms 46824 KB Output is correct
2 Correct 2411 ms 46700 KB Output is correct
3 Correct 2283 ms 45876 KB Output is correct
4 Correct 1567 ms 37356 KB Output is correct
5 Correct 1286 ms 32040 KB Output is correct
6 Correct 303 ms 18656 KB Output is correct
7 Correct 110 ms 17272 KB Output is correct