oj.uz

Submission #1037855

# Submission time Handle Problem Language Result Execution time Memory
1037855 2024-07-29T09:18:22 Z vjudge1 Cities (BOI16_cities) C++17
100 / 100
 1302 ms 49960 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
ll n, k, m, d[1LL<<5][mxn];
vector<vector<pair<ll,ll>>> g(mxn);
struct node {ll u, dist;};
struct cmp {bool operator() (node a, node b) {return a.dist > b.dist;}};
void dijkstra(ll id)
{
    priority_queue<node,vector<node>,cmp> pq;
    for (ll i = 1; i <= n; i++) pq.push({i,d[id][i]});
    while (!pq.empty())
    {
        node u = pq.top(); pq.pop();
        if (d[id][u.u] < u.dist) continue;
        for (pair<ll,ll> i : g[u.u])
        {
            if (d[id][i.fi] > d[id][u.u]+i.se)
            {
                d[id][i.fi] = d[id][u.u]+i.se;
                pq.push({i.fi,d[id][i.fi]});
            }
        }
    }   
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> k >> m;
    for (ll i = 0; i < (1LL<<k); i++) for (ll j = 1; j <= n; j++) d[i][j] = 1e18;
    for (ll i = 0; i < k; i++) 
    {
        ll x; cin >> x;
        d[1LL<<i][x] = 0;
    }
    for (ll i = 1; i <= m; i++)
    {
        ll a, b, w; cin >> a >> b >> w;
        g[a].pb({b,w}); g[b].pb({a,w});
    }
    for (ll i = 0; i < (1LL<<k); i++)
    {
        for (ll j = i; j > 0; j = (j-1)&i)
        {
            for (ll kk = 1; kk <= n; kk++) d[i][kk] = min(d[i][kk],d[i^j][kk]+d[j][kk]);
        }
        dijkstra(i);
    }
    ll opt = 1e18;
    for (ll i = 1; i <= n; i++) opt = min(opt, d[(1LL<<k)-1][i]);
    cout << opt;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 3 ms 27228 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 31756 KB Output is correct
2 Correct 325 ms 30640 KB Output is correct
3 Correct 214 ms 20092 KB Output is correct
4 Correct 43 ms 21460 KB Output is correct
5 Correct 181 ms 28480 KB Output is correct
6 Correct 40 ms 19280 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 2 ms 7048 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15192 KB Output is correct
2 Correct 5 ms 15284 KB Output is correct
3 Correct 4 ms 15196 KB Output is correct
4 Correct 4 ms 15196 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 39384 KB Output is correct
2 Correct 626 ms 38424 KB Output is correct
3 Correct 418 ms 28332 KB Output is correct
4 Correct 351 ms 33488 KB Output is correct
5 Correct 103 ms 29184 KB Output is correct
6 Correct 48 ms 29780 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1188 ms 49960 KB Output is correct
2 Correct 1302 ms 49616 KB Output is correct
3 Correct 1151 ms 48796 KB Output is correct
4 Correct 828 ms 38928 KB Output is correct
5 Correct 642 ms 45900 KB Output is correct
6 Correct 156 ms 41784 KB Output is correct
7 Correct 55 ms 42352 KB Output is correct