oj.uz

Submission #559982

# Submission time Handle Problem Language Result Execution time Memory
559982 2022-05-11T02:10:02 Z Huy Cities (BOI16_cities) C++17
100 / 100
 2037 ms 46624 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 27372 KB Output is correct
2 Correct 450 ms 26756 KB Output is correct
3 Correct 246 ms 19600 KB Output is correct
4 Correct 63 ms 10328 KB Output is correct
5 Correct 254 ms 21992 KB Output is correct
6 Correct 57 ms 10248 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 34756 KB Output is correct
2 Correct 893 ms 33196 KB Output is correct
3 Correct 597 ms 26108 KB Output is correct
4 Correct 535 ms 23416 KB Output is correct
5 Correct 157 ms 12792 KB Output is correct
6 Correct 68 ms 12744 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2037 ms 46624 KB Output is correct
2 Correct 1967 ms 46568 KB Output is correct
3 Correct 1847 ms 46172 KB Output is correct
4 Correct 1288 ms 38800 KB Output is correct
5 Correct 1010 ms 29520 KB Output is correct
6 Correct 245 ms 14120 KB Output is correct
7 Correct 82 ms 12844 KB Output is correct