oj.uz

Submission #526289

# Submission time Handle Problem Language Result Execution time Memory
526289 2022-02-14T07:57:53 Z acyme_nom Cities (BOI16_cities) C++14
100 / 100
 1862 ms 121168 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;
vector <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].push_back(ii(c,v));
        adj[v].push_back(ii(c,u));
    }
    for(int u=1; u<=n; u++)
        sort(adj[u].begin(),adj[u].end());
}

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 2 ms 3292 KB Output is correct
2 Correct 2 ms 3284 KB Output is correct
3 Correct 2 ms 3288 KB Output is correct
4 Correct 2 ms 3288 KB Output is correct
5 Correct 3 ms 3288 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 121168 KB Output is correct
2 Correct 481 ms 120492 KB Output is correct
3 Correct 288 ms 112936 KB Output is correct
4 Correct 62 ms 14740 KB Output is correct
5 Correct 286 ms 118812 KB Output is correct
6 Correct 49 ms 14700 KB Output is correct
7 Correct 6 ms 4428 KB Output is correct
8 Correct 3 ms 4448 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4428 KB Output is correct
2 Correct 6 ms 4440 KB Output is correct
3 Correct 5 ms 4428 KB Output is correct
4 Correct 4 ms 3916 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 933 ms 120920 KB Output is correct
2 Correct 910 ms 120396 KB Output is correct
3 Correct 635 ms 113068 KB Output is correct
4 Correct 512 ms 68952 KB Output is correct
5 Correct 136 ms 24452 KB Output is correct
6 Correct 58 ms 16616 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1860 ms 121000 KB Output is correct
2 Correct 1862 ms 121120 KB Output is correct
3 Correct 1720 ms 120376 KB Output is correct
4 Correct 1202 ms 113124 KB Output is correct
5 Correct 936 ms 68748 KB Output is correct
6 Correct 210 ms 24572 KB Output is correct
7 Correct 67 ms 16664 KB Output is correct