Submission #1126015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126015		_rain_	Voting Cities (NOI22_votingcity)	C++20	100 / 100	75 ms	8676 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define Task "VOTINGCITY"
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define F first
#define S second

typedef pair<int, int> ii;
typedef pair<ll, int> li;

const int N = 5e3 + 5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

template<class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }

int numNode, numEdge, numQuery, numSpec;
int specNode[N];
vector<ii> adj[N];

struct EDGE {
    int u, v, w;
} edges[2 * N];

struct QUERY {
    int s;
    int price[6];
} query[105];

ll dist[N];

void dijkstra(int s) {
    priority_queue<li, vector<li>, greater<li>> pq;
    pq.push({0, s});
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    while (!pq.empty()) {
        li p = pq.top();
        pq.pop();
        int u = p.S;
        ll d = p.F;
        if (d > dist[u]) continue;
        for (ii e : adj[u]) {
            int v = e.F, w = e.S;
            if (minimize(dist[v], dist[u] + w)) 
                pq.push({dist[v], v});
        }
    }
}

namespace sub8 {
    // + build a new directed graph that contain all nodes of the base graph and reverse all edges of the base graph
    // + create a new super source (n + 1) that has edges to special nodes with w = 0
    // + then run dijkstra as subtask 7 from the super source to other nodes
    // + then for each query, we just need to consider the shortest path from the super source to s, because if we want to reach s, we must pass through one of the special nodes, because the super source only has edge from it to special nodes
    
    vector<ii> newADJ[N];

    void buildADJ() {
        FOR(i, 1, numEdge) {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            newADJ[v].push_back({u, w});
        }
        int newNode = numNode + 1;
        FOR(i, 1, numSpec) newADJ[newNode].push_back({specNode[i], 0});
    }

    bool isValidMask(int mask, int queryID) {
        FOR(i, 0, 4) if (mask >> i & 1) {
            if (query[queryID].price[i + 1] == -1) return false;
        }
        return true;
    }

    struct STATE {
        int u;
        long long dist;
        int mask;

        bool operator < (const STATE &other) const {
            return dist > other.dist;
        }
    };

    void printMask(int mask) {
        FOR(i, 0, 4) cout << (mask >> i & 1);
    }

    ll dist[N][33];

    void dijkstra(int s) {
        priority_queue<STATE> pq;
        pq.push({s, 0, 0});
        memset(dist, 0x3f, sizeof(dist));
        dist[s][0] = 0;
        while (!pq.empty()) {
            STATE t = pq.top();
            pq.pop();
            int u = t.u, preMask = t.mask;
            long long d = t.dist;
            if (d > dist[u][preMask]) continue;
            // cout << u << ": dist: " << d << ", mask: ";
            // printMask(preMask);
            // cout << "\n";
            for (ii e : newADJ[u]) {
                int v = e.F, w = e.S;
                if (minimize(dist[v][preMask], dist[u][preMask] + 1LL * w))
                    pq.push({v, dist[v][preMask], preMask});
                FOR(i, 0, 4) if (!(preMask >> i & 1)) {
                    int newMask = (preMask | (1 << i));
                    if (minimize(dist[v][newMask], dist[u][preMask] + 1LL * w - 1LL * w * (i + 1) / 10))
                        pq.push({v, dist[v][newMask], newMask});
                }
            }
        }
    }   

    void solve() {
        buildADJ();
        dijkstra(numNode + 1);
        FOR(t, 1, numQuery) {
            int s = query[t].s;
            ll ans = dist[0][0];
            FOR(mask, 0, (1 << 5) - 1) if (isValidMask(mask, t)) {
                ll ticketCost = 0;
                FOR(k, 0, 4) if (mask >> k & 1) ticketCost += query[t].price[k + 1];
                minimize(ans, dist[s][mask] + ticketCost);
            }
            cout << (ans == dist[0][0] ? -1 : ans) << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(Task".INP", "r")) {
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w", stdout);
    }
    
    cin >> numNode >> numEdge >> numSpec;
    FOR(i, 1, numSpec) cin >> specNode[i], specNode[i]++;
    FOR(i, 1, numEdge) {
        int u, v, w;
        cin >> u >> v >> w;
        u++;
        v++;
        edges[i] = {u, v, w};
        adj[u].push_back({v, w});
    }
    cin >> numQuery;
    FOR(i, 1, numQuery) {
        cin >> query[i].s;
        query[i].s++;
        FOR(j, 1, 5) cin >> query[i].price[j];
    }
    
    sub8::solve();

    cerr << TIME << "s\n";

    return 0;
}

Compilation message (stderr)

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