oj.uz

Submission #526228

# Submission time Handle Problem Language Result Execution time Memory
526228 2022-02-14T01:47:07 Z acyme_nom Cities (BOI16_cities) C++14
22 / 100
 406 ms 115956 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<int,int>;
#define X first
#define Y second


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

ll 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 3 ms 3308 KB Output is correct
3 Correct 3 ms 3276 KB Output is correct
4 Correct 2 ms 3276 KB Output is correct
5 Correct 2 ms 3304 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 113280 KB Output is correct
2 Correct 406 ms 115956 KB Output is correct
3 Incorrect 87 ms 108020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 5 ms 4428 KB Output is correct
3 Incorrect 3 ms 4300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 113308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 113348 KB Output isn't correct
2 Halted 0 ms 0 KB -