# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
478490 |
2021-10-07T17:50:36 Z |
Lobo |
Cities (BOI16_cities) |
C++17 |
|
3706 ms |
115332 KB |
#include <bits/stdc++.h>
using namespace std;
const long long INFll = (long long) 1e16 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 220000
ii n, k, m;
ll dd[6][maxn], d[maxn][50];
vector<pair<ii,ll>> g[maxn];
vector<ii> ci;
void shortp(ii id) {
for(ii i = 1; i <= n; i++) {
dd[id][i] = INFll;
}
dd[id][ci[id]] = 0;
priority_queue<pair<ll,ii>> pq; pq.push(mp(0,ci[id]));
while(pq.size()) {
ii u = pq.top().sc;
ll dist = -pq.top().fr;
pq.pop();
if(dist != dd[id][u]) continue;
for(auto V : g[u]) {
ii v = V.fr;
ll w = V.sc;
if(dd[id][u] + w < dd[id][v]) {
dd[id][v] = dd[id][u] + w;
pq.push(mp(-dd[id][v],v));
}
}
}
}
void shortp1() {
priority_queue<pair<ll,pair<ii,ii>>> pq;
for(ii i = 1; i <= n; i++) {
for(ii mask = 0; mask < (1<<k); mask++) {
d[i][mask] = 0;
for(ii id = 0; id < k; id++) {
if((mask&(1<<id)) != 0) d[i][mask]+= dd[id][i];
}
pq.push(mp(-d[i][mask],mp(i,mask)));
}
}
while(pq.size()) {
ii u = pq.top().sc.fr;
ii mask = pq.top().sc.sc;
ll dist = -pq.top().fr;
pq.pop();
if(dist != d[u][mask]) continue;
for(auto V : g[u]) {
ii v = V.fr;
ll w = V.sc;
for(ii id = 0; id < k; id++) {
if((mask&(1<<id)) != 0) continue;
ii mask1 = mask|(1<<id);
if(d[v][mask1] > d[u][mask] + w + dd[id][v]) {
d[v][mask1] = d[u][mask] + w + dd[id][v];
pq.push(mp(-d[v][mask],mp(v,mask1)));
}
}
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
//freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
cin >> n >> k >> m;
for(ii i = 0; i < k; i++) {
ii x; cin >> x;
ci.pb(x);
}
for(ii i = 0; i < m; i++) {
ii u, v;
ll w;
cin >> u >> v >> w;
g[u].pb(mp(v,w));
g[v].pb(mp(u,w));
}
for(ii i = 0; i < k; i++) {
shortp(i);
}
shortp1();
ll ans = INFll;
for(ii i = 1; i <= n; i++) {
ans = min(ans, d[i][(1<<k)-1]);
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5456 KB |
Output is correct |
2 |
Correct |
3 ms |
5456 KB |
Output is correct |
3 |
Correct |
3 ms |
5496 KB |
Output is correct |
4 |
Incorrect |
3 ms |
5556 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
894 ms |
74168 KB |
Output is correct |
2 |
Correct |
889 ms |
73328 KB |
Output is correct |
3 |
Correct |
624 ms |
67164 KB |
Output is correct |
4 |
Correct |
94 ms |
18424 KB |
Output is correct |
5 |
Correct |
480 ms |
67256 KB |
Output is correct |
6 |
Correct |
84 ms |
18228 KB |
Output is correct |
7 |
Correct |
7 ms |
6276 KB |
Output is correct |
8 |
Correct |
6 ms |
6096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
6352 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1751 ms |
87452 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3706 ms |
115332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |