# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
84879 |
2018-11-17T16:42:00 Z |
atoiz |
Cities (BOI16_cities) |
C++14 |
|
2761 ms |
42732 KB |
#pragma GCC optimize ("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
using namespace std;
#define fi first
#define se second
#define int long long
const int INF = 1e17;
const int MAX = 100100;
int n, k, m;
int spec[5];
vector< pair<int, int> > G[MAX];
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
int ans[32][MAX];
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k >> m;
for (int i = 0; i < k; ++i) cin >> spec[i];
for (int i = 0; i < m; ++i) {
int u, v, c; cin >> u >> v >> c;
G[u].push_back({c, v});
G[v].push_back({c, u});
}
for (int i = 0; i < (1 << k); ++i) {
for (int j = 1; j <= n; ++j) {
ans[i][j] = INF;
}
}
for (int i = 0; i < k; ++i) {
ans[1 << i][spec[i]] = 0;
}
for (int mask = 1; mask < (1 << k); ++mask) {
for (int i = 0; i < k; ++i) if ((mask >> i) & 1) {
for (int u = 1; u <= n; ++u) {
ans[mask][u] = min(ans[mask][u], ans[mask ^ (1 << i)][u] + ans[1 << i][u]);
}
}
for (int u = 1; u <= n; ++u) pq.push({ans[mask][u], u});
while (!pq.empty()) {
pair<int, int> cur = pq.top(); pq.pop();
if (ans[mask][cur.se] < cur.fi) continue;
ans[mask][cur.se] = cur.fi;
for (pair<int, int> e : G[cur.se]) {
if (ans[mask][e.se] > cur.fi + e.fi) {
ans[mask][e.se] = cur.fi + e.fi;
pq.push({ans[mask][e.se], e.se});
}
}
}
}
int final_ans = INF;
for (int u = 1; u <= n; ++u) final_ans = min(final_ans, ans[(1 << k) - 1][u]);
cout << final_ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2684 KB |
Output is correct |
2 |
Correct |
5 ms |
2812 KB |
Output is correct |
3 |
Correct |
5 ms |
2880 KB |
Output is correct |
4 |
Correct |
6 ms |
2880 KB |
Output is correct |
5 |
Correct |
5 ms |
3020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
752 ms |
23684 KB |
Output is correct |
2 |
Correct |
724 ms |
23684 KB |
Output is correct |
3 |
Correct |
485 ms |
23684 KB |
Output is correct |
4 |
Correct |
116 ms |
23684 KB |
Output is correct |
5 |
Correct |
412 ms |
23684 KB |
Output is correct |
6 |
Correct |
93 ms |
23684 KB |
Output is correct |
7 |
Correct |
7 ms |
23684 KB |
Output is correct |
8 |
Correct |
6 ms |
23684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
23684 KB |
Output is correct |
2 |
Correct |
10 ms |
23684 KB |
Output is correct |
3 |
Correct |
8 ms |
23684 KB |
Output is correct |
4 |
Correct |
8 ms |
23684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1340 ms |
30072 KB |
Output is correct |
2 |
Correct |
1344 ms |
30072 KB |
Output is correct |
3 |
Correct |
931 ms |
30072 KB |
Output is correct |
4 |
Correct |
771 ms |
30072 KB |
Output is correct |
5 |
Correct |
223 ms |
30072 KB |
Output is correct |
6 |
Correct |
100 ms |
30072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2761 ms |
42732 KB |
Output is correct |
2 |
Correct |
2711 ms |
42732 KB |
Output is correct |
3 |
Correct |
2683 ms |
42732 KB |
Output is correct |
4 |
Correct |
1957 ms |
42732 KB |
Output is correct |
5 |
Correct |
1446 ms |
42732 KB |
Output is correct |
6 |
Correct |
707 ms |
42732 KB |
Output is correct |
7 |
Correct |
105 ms |
42732 KB |
Output is correct |