Submission #1281442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281442		cheska	Voting Cities (NOI22_votingcity)	C++20	25 / 100	1094 ms	2624 KiB

Main

//dominater orz
//evenvalue orz
//roumak orz
//melody orz
//cpp orz
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<pii, pii> 
#define tiii tuple<int, int, int>
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
#define f first
#define s second
#define pb push_back
const int N = 2e5+5;
const int MOD = 1e9+7;
vector<int> dijkstra(int s, int n, vector<vector<pii>> a) {
    priority_queue<pii, vector<pii>, greater<pii>> q; q.push({0, s});
    vector<int> d(n, LLONG_MAX);
    d[s] = 0;
    while (!q.empty()) {
        pii u = q.top(); q.pop();
        if (u.f > d[u.s]) continue;
        for (pii v : a[u.s]) {
            if (d[v.f] > d[u.s]+v.s) {
                d[v.f] = d[u.s]+v.s;
                q.push({d[v.f], v.f});
            }
        }
    }
    return d;
}
signed main() {
  //  freopen("in.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
    vector<int> t;
    for (int i = 0; i < k; i++) {
        int j; cin >> j; t.pb(j);
    }
    vector<vector<pii>> a(n);
    while (m--) {
        int u, v, w; cin >> u >> v >> w;
        a[u].pb({v, w});
    }
    int q; cin >> q;
    while (q--) {
        int s; cin >> s;
        vector<int> p(5);
        for (int i = 0; i < 5; i++) cin >> p[i];
        vector<vector<int>> ans(32, vector<int>(n, LLONG_MAX));
        ans[0] = dijkstra(s, n, a);
        for (int i = 1; i < 32; i++) {
            priority_queue<pii, vector<pii>, greater<pii>> pq;
            for (int j = 0; j < n; j++) {
                for (pii l : a[j]) {
                    for (int o = 0; o < 5; o++) {
                        if (i&(1<<o)) {
                            if (ans[i-(1<<o)][j] == LLONG_MAX) continue;
                            int x = l.s*(10-o-1)/10;
                            ans[i][l.f] = min(ans[i][l.f], ans[i-(1<<o)][j]+x);
                        }
                    }
                }
            }
            for (int j = 0; j < n; j++) {
                if (ans[i][j] != LLONG_MAX && j != s) pq.push({ans[i][j], j});
            }
            ans[i][s] = 0; pq.push({0, s});
            while (!pq.empty()) {
                pii u = pq.top(); pq.pop();
                if (u.f > ans[i][u.s]) continue;
                for (pii v : a[u.s]) {
                    if (ans[i][v.f] > v.s+u.f) {
                        ans[i][v.f] = v.s+u.f;
                        pq.push({ans[i][v.f], v.f});
                    }
                }
            }
        }
        int ans2 = LLONG_MAX;
        for (int i : t) {
            for (int j = 0; j < 32; j++) {
                if (ans[j][i] == LLONG_MAX) continue;
                bool ch = true;
                for (int l = 0; l < 5; l++) {
                    if (j&(1<<l)) {
                        if (p[l] != -1) ans[j][i] += p[l];
                        else {
                            ch = false; break;
                        }
                    }
                }
                if (!ch) continue;
                ans2 = min(ans2, ans[j][i]);
            }
        }
        if (ans2 == LLONG_MAX) cout << "-1\n";
        else cout << ans2 << '\n';
    }
}

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