//Singapore NOI 2022 - Voting Cities
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
const int INF = 1e18+7;
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, e, k;
cin >> n >> e >> k; int t[k];
vector<vector<pair<int,int>>>edges(n+1);
set<pair<int,pair<int,int>>>d;
for(int i = 0; i < k; i++){
cin >> t[i];
d.insert(mp(0,mp(t[i],0)));
}
for(int i = 0; i < e; i++){
int u, v, w;
cin >> u >> v >> w;
//edges[u].push_back({v,w});
edges[v].push_back({u,w});
}
int dp[n][100100]; bool vis[n][100100];
memset(dp,-1,sizeof(dp));
while(d.size())
{
int dist = (*d.begin()).fi;
int nd = (*d.begin()).se.fi;
int mask = (*d.begin()).se.se;
d.erase(d.begin());
if(vis[nd][mask])
continue;
dp[nd][mask] = dist;
vis[nd][mask] = 1;
for(pair<int,int> i : edges[nd]){
if(!vis[i.fi][mask])
d.insert(mp(dist+i.se,mp(i.fi, mask)));
for(int j = 0; j < 5; j++){
if(!((1<<j) & mask)){
if(!vis[i.fi][mask | (1<<j)])
d.insert(mp(dist+i.se/10ll * (10-j-1), mp(i.fi, mask | (1<<j))));
}
}
}
}
int q; cin >> q;
while(q--)
{
int p[6], s;
cin >> s;
for(int i = 0; i < 5; i++)
cin >> p[i];
int ans = 1e18;
for(int j = 0; j < 1 << 5; j++){
if(dp[s][j] != -1){
bool valid = 1; int cost = 0;
for(int k = 0; k < 5; k++){
if((1<<k) & j){
if(p[k] == -1)
valid = 0;
else
cost+=p[k];
}
}
if(valid)
ans = min(ans,dp[s][j] + cost);
}
}
if(ans == 1e18)
cout << -1 << endl;
else
cout << ans << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
401 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
401 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
401 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
401 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
401 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
325 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
91416 KB |
Output is correct |
2 |
Correct |
54 ms |
91340 KB |
Output is correct |
3 |
Correct |
41 ms |
88392 KB |
Output is correct |
4 |
Correct |
40 ms |
64496 KB |
Output is correct |
5 |
Correct |
50 ms |
82636 KB |
Output is correct |
6 |
Correct |
39 ms |
88484 KB |
Output is correct |
7 |
Correct |
52 ms |
91368 KB |
Output is correct |
8 |
Correct |
59 ms |
91472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
401 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |