Submission #559982

#	Time	Username	Problem	Language	Result	Execution time	Memory
559982		Huy	Cities (BOI16_cities)	C++17	100 / 100	2037 ms	46624 KiB

cities

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const int N = (int)5e5;
const int maxN = (int)5e5 + 5;
const ll mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e17;
const ll logn = 18;
const int base = 311;
const int Block_size = 500;
const int ep = 'a';

int cu[] = {0,0,1,-1};
int cv[] = {-1,1,0,0};

int du[] = {-1,-1,+1,1};
int dv[] = {-1,+1,-1,1};

int cled[] = {6,2,5,5,4,5,6,3,7,6};

void InputFile()
{
    freopen(".inp","r",stdin);
    freopen(".out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int n,k,m;
int spec[maxN];
vector<vector<pii>> adj;

void Read()
{
   cin >> n >> k >> m;
   adj.resize(n+1);
   for(int i = 1;i <= k;i++)
   {
       cin >> spec[i];
       spec[i]--;
   }
   for(int i = 1;i <= m;i++)
   {
       int x,y,w;
       cin >> x >> y >> w;
       x--;
       y--;
       adj[x].push_back({y,w});
       adj[y].push_back({x,w});
   }
}

int dp[(1 << 5)][maxN];
int f[maxN];

struct Tpq
{
    int ver;
    int val;
    bool operator < (const Tpq& other) const
    {
        return other.val < val;
    }
};

void Dijkstra() /// Loang
{
    priority_queue<Tpq> pq;
    for(int i = 0;i < n;i++)
    {
        if(f[i] < infty)
        {
            pq.push({i,f[i]});
        }
    }

    do
    {
        Tpq pick = pq.top();
        pq.pop();
        if(pick.val != f[pick.ver]) continue;
        int u = pick.ver;
        for(pii x : adj[u])
        {
            if(f[x.fi] > f[u] + x.se)
            {
                f[x.fi] = f[u] + x.se;
                pq.push({x.fi,f[x.fi]});
            }
        }
    }
    while(!pq.empty());
}

void Solve()
{
    /// init
    for(int i = 0;i < n;i++)
    {
        for(int mask = 0;mask < (1 << k);mask++)
        {
            dp[mask][i] = infty;
            if(mask == 0) dp[mask][i] = 0;
        }
    }
    for(int i = 1;i <= k;i++)
    {
        dp[(1<<(i-1))][spec[i]] = 0;
        dp[0][spec[i]] = infty;
    }

    ///
    for(int mask = 1;mask < (1 << k);mask++)
    {
        for(int i = 0;i < n;i++)
        {
            for(int pre_mask1 = 1;pre_mask1 < (1 << k);pre_mask1++)
            {
                if((mask & pre_mask1) == pre_mask1)
                {
                    int pre_mask2 = mask ^ pre_mask1;
                    dp[mask][i] = min(dp[mask][i],dp[pre_mask1][i] + dp[pre_mask2][i]);
                }
            }
        }
        for(int i = 0;i < n;i++)
        {
            f[i] = dp[mask][i];
        }
        Dijkstra();
        for(int i = 0;i < n;i++)
        {
            dp[mask][i] = f[i];
        }
    }

    ///
    int res = infty;
    for(int i = 0;i < n;i++)
    {
        res = min(res,dp[(1<<k)-1][i]);
    }
    cout << res;
}

void Debug()
{
    //Main_sub();
    //Naive();
}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Compilation message (stderr)

cities.cpp: In function 'void InputFile()':
cities.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen(".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
cities.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen(".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26