Submission #1238978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238978		cowwycow	Voting Cities (NOI22_votingcity)	C++20	100 / 100	161 ms	35516 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
#define endl "\n"
#define fi first
#define se second
using ll = long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ppii = pair<int, pii>;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using pdb = pair<db, db>;

bool bit(int i, int j){
    return i >> j & 1;
}

const int N = 5e3 + 5, M = (1 << 5) + 3, K = N * M;
const ll inf = 1e18;

vector<pll> e[K];

ll d[K];
vector<int> source;

void dijkstra(){
    for(int i = 0; i < K; i++){
        d[i] = inf;
    }
    for(int i = 0; i < source.size(); i++){
        d[source[i]] = 0;
    }
    priority_queue<pll, vector<pll>, greater<pll> > pq;
    for(int i = 0; i < source.size(); i++){
        pq.push({0, source[i]});
    }

    while(!pq.empty()){
        ll distu = pq.top().first; int u = pq.top().second;
        pq.pop();
        if(distu != d[u]){
            continue;
        }
        for(auto [v, len] : e[u]){
            if(d[u] + len < d[v]){
                d[v] = d[u] + len;
                pq.push({d[v], v});
            }
        }
    }
}

ll price[6];

void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    while(k--){
        int x; cin >> x; source.push_back(x);
    }

    int lim = 1 << 5;

    while(m--){
        int u, v; ll w;
        cin >> u >> v >> w;
        swap(v, u);
        for(int i = 0; i < lim; i++){
            e[i * n + u].push_back({i * n + v, w});
            for(int j = 1; j <= 5; j++){
                if(bit(i, j - 1) == false){
                    int cur = i ^ (1 << (j - 1));
                    e[i * n + u].push_back({cur * n + v, w / 10 * (10 - j)});
                }
            }
        }
    }

    dijkstra();

    int q; cin >> q;
    while(q--){
        int start; cin >> start;
        for(int i = 1; i <= 5; i++){
            cin >> price[i];
        }

        ll ans = inf;
        for(int i = 0; i < lim; i++){
            bool possible = true;
            ll sump = 0;
            for(int j = 1; j <= 5; j++){
                if(bit(i, j - 1)){
                    if(price[j] == -1) possible = false;
                    else sump += price[j];
                }
            }
            if(possible == true){
                ans = min(ans, d[i * n + start] + sump);
            }
        }
        cout << (ans >= inf ? -1 : ans) << endl;
    }
}

int main(){
    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    int test = 1;
    //cin >> test;
    while(test--){
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(name".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