Submission #1182607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182607		vukhacminh	Voting Cities (NOI22_votingcity)	C++20	100 / 100	64 ms	8376 KiB

Main

/**
*    Author :  Vu Khac Minh
*    Created : 08.03.2024
**/
#include <bits/stdc++.h>
#define MASK(x) ((1ll) << (x))
#define BIT(x, i) (((x) >> (i)) & (1))
#define c_bit(i) __builtin_popcountll(i) 
#define SET_ON(x, i) ((x) | MASK(i)) 
#define SET_OFF(x, i) ((x) & ~MASK(i)) 
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = " << (val) << "] "
#define ll long long
#define int long long 
using namespace std;
const int maxn = 5e3 + 5;
const int mod = 1e9+7;
void file()
{
    #define Task "ROUNDPRI"
    if(fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        freopen(Task".out","w",stdout);
    }
}
ll n,m,k,st[maxn],dp[maxn][MASK(5)],nquery,bonus[maxn];
vector<pair<int,int>> adj[maxn];
void solve()
{
    cin>>n>>m>>k;
    FOR(i,1,k) cin>>st[i];
    FOR(i,1,m)
    {
        int u,v,w;
        cin>>u>>v>>w;
        adj[v].push_back({u,w});
    }
    FOR(i,0,n)
        FOR(mask,0,MASK(5)-1)
         dp[i][mask] = 1e15;
    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
    FOR(i,1,k)
    {
        pq.push({0,{st[i],0}});
        dp[st[i]][0] = 0;
        // cout << st[i] << endl;
    }
    while(pq.size())
    {
        ll du = pq.top().first;
        ll u = pq.top().second.first;
        ll mask = pq.top().second.second;
        pq.pop();
        if(du!=dp[u][mask]) continue;
        // cout << u << ' ' << du << endl;
        for(auto i : adj[u])
        {
            int v = i.first,w = i.second;
            if(dp[v][mask] > du + w)
            {
                dp[v][mask] = du + w;
                pq.push({dp[v][mask],{v,mask}});
                // cout << v << ' ' << w << ' ' << mask << ' ' << dp[v][mask] << endl;
            }
            FOR(j,0,4)
            {
                if(!BIT(mask,j))
                {
                    int newd = du + (w/10 * (9-j));
                    if(dp[v][mask|MASK(j)] > newd)
                    {
                        dp[v][mask|MASK(j)] = newd;
                        pq.push({dp[v][mask|MASK(j)],{v,mask|MASK(j)}});
                    }
                }
            }
        }
        
    }
   /* FOR(i,0,n)
        FOR(mask,0,MASK(5)-1)
        {
            cout<<mask<<" "<<i<<" "<<dp[i][mask]<<'\n';
        }*/
    cin>>nquery;
    while(nquery--)
    {
        int s;
        cin>>s;
        FOR(i,0,4) 
        {
            cin>>bonus[i];
            if(bonus[i] == -1) bonus[i] = 1e15;
        }
        ll res = 1e15;
        FOR(mask,0,MASK(5)-1)
        {
            ll val  = dp[s][mask];
            FOR(i,0,4)
            if(BIT(mask,i))
                val+=bonus[i];
            res = min(res,val);
        }
        if(res == 1e15) cout<<-1<<'\n';
        else cout<<res<<'\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    file();
    //cin >> ntest;
    while (ntest--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void file()':
Main.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(Task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 50 / 50