oj.uz

Submission #526229

# Submission time Handle Problem Language Result Execution time Memory
526229 2022-02-14T01:48:47 Z acyme_nom Cities (BOI16_cities) C++14
100 / 100
 1938 ms 123840 KB 
/// acyme_nom ///
#include <bits/stdc++.h>

using namespace std;

#define task "thanh"

#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


#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()
{
    cin >> n >> k >> 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;
        cin >> x;
        dp[1<<(i-1)][x] = 0;

    }

    for(int i=1; i<=m; i++)
    {
        int u,v,c;
        cin >> u >> v >> c;
        adj[u].push_back(ii(c,v));
        adj[v].push_back(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]);

    cout << ans <<'\n';
}

int32_t main()
{
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);

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

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

    return 0;
}

Compilation message

cities.cpp: In function 'int32_t main()':
cities.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 119516 KB Output is correct
2 Correct 446 ms 119008 KB Output is correct
3 Correct 287 ms 111712 KB Output is correct
4 Correct 60 ms 16836 KB Output is correct
5 Correct 292 ms 121640 KB Output is correct
6 Correct 58 ms 16892 KB Output is correct
7 Correct 4 ms 4476 KB Output is correct
8 Correct 4 ms 4556 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 7 ms 4480 KB Output is correct
3 Correct 5 ms 4428 KB Output is correct
4 Correct 5 ms 3956 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 982 ms 119600 KB Output is correct
2 Correct 919 ms 123296 KB Output is correct
3 Correct 569 ms 113860 KB Output is correct
4 Correct 518 ms 71868 KB Output is correct
5 Correct 147 ms 26964 KB Output is correct
6 Correct 63 ms 18984 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1872 ms 119688 KB Output is correct
2 Correct 1938 ms 123840 KB Output is correct
3 Correct 1855 ms 123336 KB Output is correct
4 Correct 1291 ms 113880 KB Output is correct
5 Correct 1008 ms 71496 KB Output is correct
6 Correct 229 ms 26996 KB Output is correct
7 Correct 73 ms 18736 KB Output is correct