Submission #1211055

#TimeUsernameProblemLanguageResultExecution timeMemory
121105512345678Voting Cities (NOI22_votingcity)C++20
100 / 100
89 ms8344 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const ll nx=5e3+5, inf=1e18, kx=5; ll n, m, k, q, t, u, v, w, mn[nx][1<<kx], p[5]; vector<pair<ll, ll>> rv[nx]; priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>> pq; ll discount(ll x, ll t) { return (x/10)*(9-t); } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m>>k; for (int i=0; i<n; i++) for (int j=0; j<(1<<5); j++) mn[i][j]=inf; for (int i=1; i<=k;i ++) cin>>t, mn[t][0]=0, pq.push({0, t, 0}); for (int i=1; i<=m; i++) cin>>u>>v>>w, rv[v].push_back({u, w}); while (!pq.empty()) { auto [w, u, msk]=pq.top(); pq.pop(); if (mn[u][msk]<w) continue; for (auto [v, nw]:rv[u]) { //cout<<"v "<<v<<' '<<nw<<'\n'; if (mn[v][msk]>w+nw) mn[v][msk]=w+nw, pq.push({mn[v][msk], v, msk}); for (int i=0; i<5; i++) if (!(msk&(1<<i))&&mn[v][msk|(1<<i)]>w+discount(nw, i)) mn[v][msk|(1<<i)]=w+discount(nw, i), pq.push({mn[v][msk|(1<<i)], v, msk|(1<<i)}); } } cin>>q; while (q--) { cin>>u; for (int i=0; i<5; i++) cin>>p[i]; ll res=inf; for (int msk=0; msk<(1<<5); msk++) { int f=0; for (int i=0; i<5; i++) if ((msk&(1<<i))&&p[i]==-1) f=1; if (f) continue; ll sm=0; for (int i=0; i<5; i++) if (msk&(1<<i)) sm+=p[i]; res=min(res, mn[u][msk]+sm); } if (res==inf) cout<<-1<<'\n'; else cout<<res<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...