oj.uz

Submission #526305

# Submission time Handle Problem Language Result Execution time Memory
526305 2022-02-14T08:49:27 Z wai_hoang_0912 Cities (BOI16_cities) C++17
100 / 100
 2028 ms 45620 KB 
#include <bits/stdc++.h>

using namespace std;

#define FORU(i, a, b) for(__typeof(b) i = a; i <= b; i ++)
#define FORD(i, b, a) for(__typeof(b) i = b; i >= a; i --)
#define UFOR(i, a, b) for(__typeof(b) i = a; i < b; i ++)
#define DFOR(i, b, a) for(__typeof(b) i = b; i > a; i --)
#define N 100005
#define oo 1000000000000000
#define pb push_back
#define fi first
#define se second
#define ll long long

typedef pair < ll, int > ii;
int n, k, m, s[8];
ll f[1 << 8][N];
vector < ii > a[N];

void read()
{
    cin >> n >> k >> m;
    FORU(i, 1, k)
        cin >> s[i];
    int u, v;
    ll c;
    FORU(i, 1, m)
    {
        cin >> u >> v >> c;
        a[u].pb(ii(c, v));
        a[v].pb(ii(c, u));
    }
}

void Dijkstra(int mask)
{
    priority_queue < ii, vector < ii >, greater < ii > > q;
    FORU(i, 1, n)
        if(f[mask][i] != oo)
            q.push(ii(f[mask][i], i));
    while(!q.empty())
    {
        int u = q.top().se;
        ll du = q.top().fi;
        q.pop();
        if(du != f[mask][u])
            continue;
        UFOR(i, 0, a[u].size())
        {
            int v = a[u][i].se;
            ll uv = a[u][i].fi;
            if(f[mask][v] > f[mask][u] + uv)
            {
                f[mask][v] = f[mask][u] + uv;
                q.push(ii(f[mask][v], v));
            }
        }
    }
}

void solve()
{
    FORU(i, 0, 1 << k)
        FORU(j, 1, n)
            f[i][j] = oo;
    FORU(i, 1, k)
        f[1 << (i - 1)][s[i]] = 0;
    UFOR(x, 1, 1 << k)
    {
        UFOR(y, 0, x)
        {
            if((x | y) != x)
                continue;
            int z = x ^ y;
            if(y > z)
                continue;
            FORU(i, 1, n)
                f[x][i] = min(f[x][i], f[y][i] + f[z][i]);
        }
        Dijkstra(x);
    }
    ll res = oo;
    FORU(i, 1, n)
        res = min(res, f[(1 << k) - 1][i]);
    if(res == oo)
        cout << -1;
    else
        cout << res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    read();
    solve();
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2624 KB Output is correct
3 Correct 3 ms 2676 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 3 ms 2804 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 26632 KB Output is correct
2 Correct 536 ms 26124 KB Output is correct
3 Correct 302 ms 18920 KB Output is correct
4 Correct 67 ms 12084 KB Output is correct
5 Correct 271 ms 21356 KB Output is correct
6 Correct 57 ms 11948 KB Output is correct
7 Correct 5 ms 2940 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2992 KB Output is correct
2 Correct 9 ms 3068 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 7 ms 2892 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 33192 KB Output is correct
2 Correct 1052 ms 32416 KB Output is correct
3 Correct 637 ms 25284 KB Output is correct
4 Correct 595 ms 23812 KB Output is correct
5 Correct 179 ms 14248 KB Output is correct
6 Correct 91 ms 14284 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2028 ms 45608 KB Output is correct
2 Correct 1981 ms 45620 KB Output is correct
3 Correct 1904 ms 44948 KB Output is correct
4 Correct 1328 ms 37768 KB Output is correct
5 Correct 1057 ms 30092 KB Output is correct
6 Correct 294 ms 15556 KB Output is correct
7 Correct 102 ms 14664 KB Output is correct