Submission #526229

#	Time	Username	Problem	Language	Result	Execution time	Memory
526229		acyme_nom	Cities (BOI16_cities)	C++14	100 / 100	1938 ms	123840 KiB

cities

/// 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 (stderr)

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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26