oj.uz

Submission #526290

# Submission time Handle Problem Language Result Execution time Memory
526290 2022-02-14T07:59:07 Z acyme_nom Cities (BOI16_cities) C++14
100 / 100
 2950 ms 137220 KB 
/// acyme_nom ///
#include <bits/stdc++.h>

using namespace std;

#define task "CITIESK"

#define BUG(x) {cout << #x << " = " << x << '\n';}
#define PR(x,l,r) {cout << #x << " = "; for(int i=l; i<=r; i++) cout << x[i] << ' '; cout << '\n';}
#define MAXN 100011

using ld = long double;
using ll = long long;
using ii = pair<ll,ll>;
#define X first
#define Y second

template <typename T> inline void read(T & x)
{
    char c; bool nega=0;
    while((!isdigit(c=getchar()))&&c!='-');
    if(c=='-')
    {
        c=getchar();
        nega=1;
    }
    x=c-48;
    while(isdigit(c=getchar()))
    {
        x=x*10+c-48;
    }
    if(nega) x=-x;
}
template <typename T> void Write(T x)
{if (x > 9) Write(x/10); putchar(x%10+48);}
template <typename T> void write(T x)
{if (x < 0) {putchar('-'); x = -x;} Write(x);}



#define int long long
int n,m,k;
set <ii> adj[MAXN];

int dp[1<<7][MAXN];
/// dp[S][i] da di duoc tap S, dang o dinh i

void read()
{
    read(n);
    read(k);
    read(m);

    for(int mask=0; mask<(1<<7); mask++)
        for(int i=1; i<=n; i++)
            dp[mask][i] = 1e18;
    for(int i=1; i<=k; i++)
    {
        int x;
        read(x);
        dp[1<<(i-1)][x] = 0;

    }

    for(int i=1; i<=m; i++)
    {
        int u,v,c;
        read(u);
        read(v);
        read(c);
        adj[u].insert(ii(c,v));
        adj[v].insert(ii(c,u));
    }
}

void solve()
{
    for(int mask = 0; mask<(1<<k); mask++)
    {
        for(int submask = mask; submask; submask = (submask-1)&mask)
        {
            if(submask==mask) continue;

            for(int i=1; i<=n; i++)
            {
                dp[mask][i] = min(dp[mask][i],dp[mask^submask][i] + dp[submask][i]);
            }
        }

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

        for(int i=1; i<=n; i++)
        {
            if(dp[mask][i]<1e18)
                pq.push(ii(dp[mask][i],i));
        }

        while(!pq.empty())
        {
            int u = pq.top().Y;
            int du = pq.top().X;
            pq.pop();

            if(dp[mask][u]!=du) continue;

            for(auto e:adj[u])
            {
                if(dp[mask][e.Y]>dp[mask][u]+e.X)
                {
                    dp[mask][e.Y] = dp[mask][u] + e.X;
                    pq.push(ii(dp[mask][e.Y],e.Y));
                }
            }
        }
    }

    int fullmask = (1<<k)-1;

    int ans = 1e18;
    for(int i=1; i<=n; i++)
        ans = min(ans,dp[fullmask][i]);

    write(ans);
}

int32_t main()
{

    int t;
    t = 1;
    // cin >> t;     /// multitest

    while(t--)
    {
        read();
        solve();
    }

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5580 KB Output is correct
2 Correct 2 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5580 KB Output is correct
5 Correct 3 ms 5580 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 136564 KB Output is correct
2 Correct 771 ms 137016 KB Output is correct
3 Correct 382 ms 121332 KB Output is correct
4 Correct 517 ms 31980 KB Output is correct
5 Correct 428 ms 134384 KB Output is correct
6 Correct 353 ms 32048 KB Output is correct
7 Correct 6 ms 6988 KB Output is correct
8 Correct 4 ms 6860 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6988 KB Output is correct
2 Correct 7 ms 6988 KB Output is correct
3 Correct 5 ms 6732 KB Output is correct
4 Correct 6 ms 6476 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1513 ms 136892 KB Output is correct
2 Correct 1479 ms 137220 KB Output is correct
3 Correct 762 ms 121324 KB Output is correct
4 Correct 1169 ms 84148 KB Output is correct
5 Correct 925 ms 41628 KB Output is correct
6 Correct 858 ms 31556 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2942 ms 136920 KB Output is correct
2 Correct 2950 ms 136896 KB Output is correct
3 Correct 2893 ms 137200 KB Output is correct
4 Correct 1550 ms 121560 KB Output is correct
5 Correct 2262 ms 84136 KB Output is correct
6 Correct 1639 ms 42032 KB Output is correct
7 Correct 1515 ms 31640 KB Output is correct