# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
26251 | sgtlaugh | Cities (BOI16_cities) | C++14 | 3563 ms | 43864 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <bits/stdtr1c++.h>
#define MAXK 5
#define MAXN 100010
#define clr(ar) memset(ar, 0, sizeof(ar))
#define read() freopen("lol.txt", "r", stdin)
#define dbg(x) cout << #x << " = " << x << endl
#define ran(a, b) ((((rand() << 15) ^ rand()) % ((b) - (a) + 1)) + (a))
using namespace std;
const long long INF = 1LL << 60;
int n, k, m, special[MAXK];
long long dis[1 << MAXK][MAXN];
vector <pair<int, int> > graph[MAXN];
void dijkstra(long long dis[MAXN]){
int i, j, v, w;
priority_queue <pair<long long, int> > PQ;
for (i = 1; i <= n; i++){
if (dis[i] < INF) PQ.push(make_pair(-dis[i], i));
}
while (!PQ.empty()){
pair <long long, int> cur = PQ.top();
PQ.pop();
i = cur.second;
for (j = 0; j < graph[i].size(); j++){
v = graph[i][j].first, w = graph[i][j].second;
if (dis[v] > dis[i] + w){
dis[v] = dis[i] + w;
PQ.push(make_pair(-dis[v], v));
}
}
}
}
long long minimumSteinerTree(){
int i, j, mask, submask;
for (mask = 1; mask < (1 << k); mask++){
for (i = 1; i <= n; i++) dis[mask][i] = INF;
if (__builtin_popcount(mask) == 1){
dis[mask][special[31 - __builtin_clz(mask)]] = 0;
}
else{
for (i = 1; i <= n; i++){
for (submask = mask - 1; submask >= (submask ^ mask); submask = (submask - 1) & mask){
dis[mask][i] = min(dis[mask][i], dis[submask][i] + dis[submask ^ mask][i]);
}
}
}
dijkstra(dis[mask]);
}
return *std::min_element(dis[mask - 1] + 1, dis[mask - 1] + 1 + n);
}
int main(){
int i, j, u, v, w;
while (scanf("%d %d %d", &n, &k, &m) != EOF){
for (i = 0; i < MAXN; i++) graph[i].clear();
for (i = 0; i < k; i++) scanf("%d", &special[i]);
for (i = 0; i < m; i++){
scanf("%d %d %d", &u, &v, &w);
graph[u].push_back(make_pair(v, w));
graph[v].push_back(make_pair(u, w));
}
printf("%lld\n", minimumSteinerTree());
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |